well, I started using WMP10 and it is doing the job perfectly for me.
I finally joined the MP3 bandwagon when I realized I just don't listen to my 1200+ CDs enough. This way I can now throw various stuff on my 80GB MP3 player and play them at random.
Thanks for all the thoughts!