Ah, I used to (and sometimes do) use Winamp for playing back karaoke in such environments, and pacemaker works just fine. It's the plugin used with the sax n' dotty hoster (which I don't use).
Maybe you have a very... discerning crowd compared to me or something, but most drunk people in a noisy bar wouldn't notice the difference in quality, especially with loud singing on top

The quality of pacemaker isn't really all that bad, and you'll probably only have to pitch-shift a very small percentage of the songs, and those will generally only be a few semitones.
It maintains the tempo of the song while changing the key, so that will add some distortion, but if it's more important to keep the sound quality high, perhaps you can change speed instead of pitch, although I'm not sure how to accurately change the pitch this way... you could probably calculate how much a percentage change would affect the pitch.
You could look into Tricerasoft's karaoke hosting programs, like Swift Elite. It does what you want, although I'm not sure if the key-changing quality is any better, and I've had kind of bad luck using it... don't like the interface much.
Ableton Live music production software can do quite good quality timestretching with many modes and parameters, so that implies that it should be able to do just as good of a job transposing and maintaining the tempo. It's an expensive and complicated program though, for what you're most likely doing... but many DJs use it for live performance now, and you can sometimes find a cheap, stripped down version bundled with certain hardware (like M-Audio's stuff).
BTW, I may have misunderstood - I wasn't sure if you meant you are hosting karaoke, or actually singing as an entertainer yourself.