Don't pay Microsoft, if your console is out of warranty, do the X-clamp replacement mod.
My friend just gave me his old RROD'd XBOX 360, I just did the X-clamp replacement mod and it's up and running, took about a day to do (I also did the 12 volt fan mod and the towel trick a few times) and runs great.
What you do is replace the X-clamps that hold the heatsinks in place with machine screws (5mm thick, 10 to 12mm long) and use washers to space it right. Take out the motherboard, then use a 3/16" drill bit to make the holes in the bottom of the metal shell wider. Then stick 8 10 to 12mm machine screws through the holes, then put a steel washer on bottom and a nylon washer on top. Then put the motherboard in, putting the screws through the heatsink holes. Then put a nylon washer on each screw followed by a steel washer. Clean off the chips and heatsinks and then apply new thermal compound (I used Arctic Silver 5, working excellently). Then put the heatsinks back on and tighten down the screws. The screws hold the chips tighter against the board, ensuring a good connection, while the new thermal paste extracts heat much better than the old stuff. The 12v fan mod makes the fans run fast, so it helps remove the heat from the heatsinks. That's what I did, it's working very well (but I just fixed it today, so I'll keep you guys updated if it fails).