xhippo's interface could feature two lists: one which contains the list of songs it knows about, and one which contains a list of songs to play in order. When the second list is empty, it picks randomly from the first list as per normal.
iTunes does this, although this idea predates it. My xhippo replacement Potamus does away with the known-songs list entirely, relying on the filesystem.