The first thing that I would recommend, from whereever you run xmms from, make sure that it's not running "soundwrapper xmms". By default any icons made when you install the program put soundwrapper in front of xmms to "improve" sound efficiency (not quality).
I have found that this causes more problems then it's worth. I had trouble with some songs and fast tracking. It would cause the files to skip or start playing really fast
The other thing I would recomend is installing the most up to date driver support for your sound card. It might just be processing straight from your CPU.
Also you might try playing songs in other programs to see if the same thing is happening. Like mplayer, totem, etc.