Yeah, I'd say you'd want to avoid those "audio sender" devices. Heck, you're running a PC with XP in the juke, just toss in a Wireless G or N usb dongle and you're done. I can't imagine a Jukebox app out there that can't play mp3's off a server via a network connection.
Juke software using only buttons shouldn't be hard to find. I prefer the touchscreen though, so I won't be much help there.
Oh. Just saw item 3. Ugh. Hmmm....
Well, one possibility would be to run JRiver Media Center on both the Juke and a Home Theater PC in your theater.
JRMC has this feature called "zones". Essentially, you'd set up the jukebox as one zone, the HTPC as another, and then any zone can effectively control any other zone.
For instance, I have JRMC running on my desktop and on a server. I've got speakers connected to my desktop, but I've also got an amp and speakers connected to my server with the speakers being outside for the patio.
I can load up JRMC on my desktop, select the Patio zone and completely control playback from my desktop.