That is the typical usecase:

I sit with my friends, drinking beer and listening to some songs that I queued up from my big library before.

After a cool song finished playing, my friend tells me that he liked the song and wants to know the band. I cannot remember and I cannot have a look, because the song has vanished from the play queue already.

Ideally the played songs should be greyed out and if I wanted to play them again, I should be able to move them to the songs in the queue that are to yet to be played.

Banshee implemented this feature with perhaps unneeded bonus features like autofill: http://versia.com/2009/09/23/updated-play-queue-in-banshee/ 

But keeping track of the songs played before is certainly a basic feature and should be added to rhythmbox as well. Maybe Zeitgeist can be used to keep track of those songs??

That would be a great feature to enhance the Rhythmbox experience (queueing up songs by middle clicking them like in Winamp would be another great feature).