Well known problem. XMMS sucks at randomizing large playlists. Attached is a patch from David Shea of the more-or-less dormant Peachtree Linux project. It corrects the randomization problem in xmms so it doesn't cycle through the same 4 or 5 songs.
Created attachment 127625 [details] xmms randomize fix
Reassigning to current xmms maintainer (myself - haven't seen this bug report before now).
Upstream CVS appears to have similar changes, see http://cvs.xmms.org/cvsweb.cgi/xmms/xmms/playlist.c.diff?r1=1.88&r2=1.89 and the last hunk of http://cvs.xmms.org/cvsweb.cgi/xmms/xmms/playlist.c.diff?r1=1.84&r2=1.85 Could you check if they work for you?
I've long since stopped using xmms in Fedora now, but looking at the upstream code, it appears that they've finally fixed that problem.
Upstream changes applied in 1.2.10-29.fc*