Foobar2000 keeps playing the same set of songs even if the order is random

Try using the Shuffle (tracks) ordering instead of random. That should create a random ordering of your playlist and work it's way through it, rather than randomly choosing a new track after the current track finishes. Note that the shuffled list is recreated when you start Foobar, and probably also when you switch or modify playlists.