The player could keep a permanent "counter" that simply incremented with each song played. (snip) The weighted shuffle algorithm could then simply sort based on this counter value.
This is already implemented, but it's not a great solution. Consider an empeg all of which you've heard about 100 times -- then synchronise a new song on. You'll hear that song 100 times before it bothers playing any of the others.
As another poster said, even though the Mark 1's "real time clock" isn't real time (the time is remembered when the power's off, but doesn't advance), it's still good enough for biasing random shuffle with. In fact, as it records the length of time the empeg's been switched on for, it's arguably better than wall time for biasing random shuffle with.
Peter