I've always found it to be quite weird that the App Store is so closed, but a person with a developer certificate and MobileProvision can install whatever he wants and can do whatever he wants so long as the apps are codesigned. $99/yr is less than a couple coffees a month (or a good sushi plate) and way less than your phone bill, and is quite worth it for the bored hacker who wants to keep the warranty.
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.