How to debug iPhone overheating when the cause is clearly not the environment when the phone is used? My iPhone 4s with iOS 5.1 started to present overheating very often: 2-4 times a day and this happened while the outside temperature is only around 18-20C and the phone was not under heavy use, in fact in half of the cases it wasn't even used.

How can I debug these?

Going with the phone to Apple store would be the next step, but I don't want to loose precious time. I could bet that this will not happen while a "genius" is playing with the phone. Also, I'm sure they will ask me to wipe the device, something I don't want to do (did it too many times and takes a lot of time to sync ~50gb of data). 

Note: Rebooting does not solve the problem!
I would advise phoning Apple first. you will be able to speak with someone regarding the overheating error you are having. 

They will more than likely tell you why, and failing that recommend that you go to an Apple store. They will look at the device and run diagnostics.

If you report an issue with a product at the store and the issue cannot be replicated they will usually replace the device with a refurb model on the spot. I have had this happen twice (the swap, not the overheating) once with an iPad and the other an iPhone 3GS, both were replaced.

Yes the sad thing is that they will need to wipe all the data if they cannot fix it after diagnostics. You will hopefully have a backup on your computer, or if you used iCloud a back-up in the cloud, which you can start to download instantly at the store.

Hope it works out for you