I purchased a 4870 from Asus with my newest build because I started getting tight on money as well, now I'm looking at 6870's to replace it. So far I've had no problems with it, its a relatively good card for its age. I'm able to run Dragon Age: Origins at full specs. If you can get a second for another 60 bucks, 120 crossfire set up of 4870's is a very nice deal. I purchased mine at $100 from newegg 7 months ago.
How hot is it getting? A 4890 should stay at reasonable temperatures, and the Vapor-X should stay even cooler than that. The Diamond 4890 I had stayed around 35C idle and below 75C under load, and that was overclocked to 935/1050. 4890's are made to be overclocked. Some people get the core up to 1000Mhz. You definitely should not have to down clock it. Maybe you need to reapply the thermal paste. Also, the memory speed does not affect the temperature much, so you can probably put that back up in any case.
My 4890 ran for two years at 75C max without a problem. I never changed the fan profile. I don't want to speak for all 4890's, but I don't think 66C is too high. In this review, both the reference and Atomic cards reached 82C on load. I wouldn't worry about 66C.