Hi NDLH,
It's interesting that I had similar issue. The thing is, I narrow down the case to the GSM Radio especially in area without good 3G signal. How I confirm this is by turning off EVERYTHING (all notification, no wifi, no bluetooth, no Apps open, no iCloud active, no Location, you name it, while turning on the GSM Radio -- with or without Data). Other "clean" state, is when I did DFU restore, set as new Device, with only default apps, and turned all off (location, wifi, bluetooth), still, the issue persists. Whenever there's only 2G signal, it tends to give "No Service" or long "Searching..." status. At some occasion, if I force to get only 2G signal on area with 3G signal, it tends to gets hotter and hotter. When the iPhone is in its holster, it will eventually give a temperature warning sign like you had.
And yes, all these heat leads to battery drain -- that's where power goes. At worst (heat up all the way), it could drain to ~20-30% / hour without even using it.
I bought my iPhone since late Feb 2012, and till now, there's really no permanent cure with all the steps available in the web.
It was Out-Of-Box with iOS, 5.0.1, tried upgrade to 5.1, then 5.1.1, all give no improvement
I'm currently expecting iOS6 to fix this issue, as it changes the baseband to 2.8.01.