Following is the gist of an off-topic response I wrote to "Random 25". As I feel it's an important point, I've entered it as a new topic.
On the iPod, play the whole random playlist. When it's finished, if you go into the playlist again, you'll find a brand-new selection of songs.
Caveat: if you skipped an unwanted song, it will still be in the list because the iPod doesn't increment the play count until it's played all the way through. You can "trick" the iPod into thinking an unwanted song has been completely played and thus remove it from the list.
Solution: while playing an unwanted song, press the Select button once to invoke scrub mode and scrub to the end of the unwanted song. The iPod will consider this a fully played song and if you've set any time-based criteria, it won't reappear in the playlist.
That's another important point. If you fail to specify songs "not played for x amount of time", the same bunch of songs will show up because you're not filtering out the songs just played.