With the current Song Request widget, the user needs to have a good idea of the song and artist name spelling, as the song needs to be on the server.
Would a jukebox feature be viable, if you took the listing of the music as it appears under the On Demand widget, though when a user selects a track, the 'play selected tracks' link would act like the Song Request widget and line it up for playing on the stream - rather than in the browser of the local device accessing the page. This would completely replace the Song Request widget as essentially it would give the same end result.
That way, when no live DJ is on, listeners could choose what to listen to, much the same as a jukebox. It'd be a more interactive online experience. I've a need for something along those lines - the listeners of the project I am working on find it more awkward to have to type, rather than just click. Especially so in social circumstances.