I've noticed that while playing music in random mode, Ejukebox dumps 2 songs to winamps playlist at a time. This way winamp knows which song is next if next is pushed on winamp. I've also noticed that when you queue songs in ejukebox it still only dumps 2 songs at a time into winamp.

I suggest that when in random mode, have ejukebox manage a communication of 10 songs at a time with winamp instead of 2 so winamp knows about the proposed queue. Then you would be able to reverse up to 10 songs ago, in the order that they were played. Also when songs are queued manually, they should all be put in winamps playlist immediately.

These are only suggestions, perhaps you've tried this and found out a reason why it isn't good... But maybe you haven't, so I thought I would run these ideas by you and maybe I will see them implimented in a future release! Great job with the project.