I noticed that Spotify doesn't play truly random tracks when shuffling is enabled, so I wrote an Android app to force Spotify to play truly random tracks in real-time. You don't have to wait for a tool to create a new playlist thereby cluttering your Spotify library. You can find it here: https://shuffle.virock.org/ https://play.google.com/store/apps/details?id=org.virock.virtualshufflev2

Does this completely randomize the play order, or does it try to apply a "smart" algorithm?

If it's the former, I may have found an answer to my wish.

Doesn't Spotify already do this?