I agree, hardware, continuous volume control beats software, discrete volume control any time.
The most annoying thing about discrete volume control (e.g. like the one on an iPad) is that the most silent volume (the first above "sound off") is sometimes still too loud - like how the dimmest display backlight setting on the Pandora can sometimes still be too bright (maybe we need a brightness wheel too?).
The most annoying thing about software volume control (besides that it is nearly always in discrete steps) is that there tend to be circumstances in which the control doesn't work or lags noticeably. The worst is when some misbehaving buggy game goes into an infinite loop while playing back annoying sound (e.g. loud white noise caused by some bug, or a repeating audio chunk), making the keyboard sufficiently unresponsive to make your frantic "WTF stop this shit! vol-down vol-down vol-down!" keypresses do anything at all.
It sounds like your problem isn't with discrete steps in general but the selection of discrete steps on devices you've used. The great thing about system software on a device like Pandora is it can be changed by the user and is heavily impacted by user feedback.
Same with your problem with software controls not working reliably.. just because this has been the case for you doesn't mean it's an intrinsic flaw. If a kernel driver handles volume control via interrupts then it shouldn't be a problem.
The problem with a hardware volume wheel is it's hard to reproduce the setting exactly, there's no possibility for visual feedback on volume changes, there's no way to lock it out or bypass it, it has variability and cross balance problems and it can wear out over time causing crackling while changing volume. A good compromise, IMO, is to have a hardware wheel (either a continuous pot or a discrete encoder or something like that) that is monitored by low-level software. That way you can get feedback, lock out/bypass, and add filtering and calibration to deal with variability and wear problems.