Banshee 1.6 will include an updated Play Queue extension. The changes are already in git master, here are a few teaser screen-shots:
Played tracks are not removed from the queue but are shown as greyed out. You can play them again if you want, drag and drop to the back of the queue, delete, etc.
The number of played tracks to show can be changed from the preferences dialogue.
You can also ask Banshee to automatically update the queue using any shuffle mode (including the new by rating and by score modes). The number of upcoming tracks can also be changed in the preferences.
The tracks are taken from the entire library or from any play list.
If you don't like what has been added, you can refresh the upcoming tracks. Or you can add more of them (thanks Sandy!)
Tracks added manually are treated differently from those that had been added automatically. When adding, they are inserted to the front of the queue but after other manually-added tracks.
Also, they are preserved when you refresh the queue.
That's about it. If you like what you saw you can try the git master version. Otherwise just wait until 1.6 is out, it shouldn't take too long.