...pays to read the first post
To the OP... take the problem to Apple anyway. Be polite and articulate about the problem and why you think they should fix it for free because it is not a "normal wear and tear" sort of problem. Make sure you know well what you're going to say before going in to the store - getting angry or not knowing what your rights are isn't going to help. I'm not sure what sort of consumer laws you have in your country, but utilise those if they will help.
If you don't have any official Apple stores in your country, try going to a reputable reseller and ask to speak to the manager. Or send an email to Steve Jobs (can't remember the address, Google it. Apparently some "executive customer relations" team reads those emails sometimes), and get on the phone to Apple and plead your case directly to them.
And before you take it in to a store or send it away to get fixed, erase all traces of those fan control programs you have used, ie do a clean reinstall and reset PRAM and SMC again, just so they don't have a reason to not fix it. Being out of warranty, they'll take any reason they can get.