@funnel: Heat gun and thermal compound on the two RSX chips. That worked fine for three times on each PS3, however the fourth time on one of them was not able to fix it and I had to replace the unit with a new slim PS3.
I'm actually getting quite adept at the process, and can have it done in about an hour, including allowing the chips to cool down for 20 minutes. Like I said though, it only works for about two months at best each time and it looks like I'll probably have to replace the second unit as well, so I'm not sure it's worth it overall. Perhaps others have had better luck though?