elmers glue? you serious?
As far as VRM and thermal pads goes, I redid the whole kit n kaboodle for one of my 5870's, GPU die, VRAM, and VRM's. Used 1mm thermal pads from
http://www.frozencpu.com/products/9435/thr-66/EK_Thermal_Pad_Sheet_-_160mm_x_155mm_x_1mm.html for the VRAM and VRM's and Shin-Etsu x23-7783d grease for the GPU core. The thermal pads themselves arent really that sticky I think; just really soft. 1025MHz core @ 1.125v, 205MHz RAM, stock heatsink with a blower-style fan I bought to replace the original stock one; operates near identically (4100 RPM @ 100% without any air restriction above the card).
Ambient temperature right now is 8.3C. Core is at 45C (+36.7C) and VRMs are at 52C (+43.7C) and 81.29 amps. I didn't use any thermal grease for the RAM or VRM's. I just made sure it was very clean using Goo Gone (citrus-based cleaner) and denatured alcohol to pick up the remaining goo gone. Also make sure your screws are pretty tight. They should have springs and the threading doesn't go all the way on the screw so it should be impossible to overtighten them.
If your temperatures are still wonky and you are sure you have good contact, it could be something wrong with the heatsink itself. I have 2 stock 5870 heatsinks. One of them runs about 15-20C hotter, no matter how many times I mount it. Maybe bad vapor chamber/heatpipes to heatsink contact.
Here's the contact I get with my thermal pads. This is from the 15-20C higher heatsink.