Thats weird. Personally, I have not ran into this problem....but then again I don't use WMP all that much, either.
If you use an IBM microdrive, then you could consider a defrag.
The only other thing I could think of is to try another player option. I use
PocketMusic and it works great, and with lots of options.
Best of luck! :)