Or could some novel proxy otherwise keep alive a tunnel to another machine in the background? The latest iSSH app says it can keep a session alive for 10 minutes in the background -- though it's not clear if it can relay significant data while backgrounded.
http://developer.apple.com/iphone/library/documentation/uiki...
"This method lets your application continue to run for a period of time after it transitions to the background."
http://developer.apple.com/iphone/library/documentation/iPho...
...it sounds like a background audio app could do arbitrary other things while remaining unsuspended, and receiving audio callbacks, as long as it also keeps playing audio. (I'm sure Apple would frown on such behavior, and ultimately thwart it, but it seems like the framework gives enough discretion to the app to do other things.)
My guess is Pandora has some fairly sophisticated server-side streaming that responds to ACK/FIN-type feedback from the iPhone client.