Considering the location, and you say the power supply isn't overly hot; the best that I can come up with is that you're getting a dead air pocket between the side of the PS and the motherboard. Having a room fan blowing on the open computer would get the air flowing through that pocket allowing it to cool better.

Newer power supplys actually have two fans; one on the back side like the traditional units (blowing out), and one underneath the unit pulling air away from the CPU. If you don't have one of these PS units, you might consider getting one. Beyond that, I don't have any ideas.