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.