I had a similar issue with Foobar until I realized that 'random' meant 'won't play song twice in a row' while 'shuffle' was more of a 'won't play song again until everything else is played'.