The power supply shouldn't do much when it comes to temperatures (unless you're running a crazy 1600 watt and all the heat it gives off superheats the case).
As a cheap hardware solution, I'd recommend picking these up:
http://www.xoxide.com/slotcooler.html
Put one under each GPU (you'll have to rip the PCI bracket off and clip it back in backwards, but you don't need any tools for that). I have 2x8800GTS 640MB, and both had their full load temperatures drop something like 15C.
Also, while some cards might be rated to work at 110C, you should never run a card above 90C (around 70 is ideal). Higher than 90C, and you're just slowly cooking your video memory and knocking a few years off its lifespan.