Actually, Eclecticos posts have been very helpful and I would suggest taking his advice.
I think the fans are probably fine, but if you could find a stronger set that might help. Adding or redoing the thermal paste is a good idea as well. Sometimes they don't even include thermal paste, they just slap on this aluminum sticker type deal and call it good. You may want to get some higher quality paste and redo it. Dust could also be a problem, so make sure everything is nice and clean. But from the sounds of it, you apparently already knew that. As for the 120mm on the side of the case, that is your best suggestion so far in this entire thread hands down. That alone may very well fix your problem. I suggest Yate Loon or Noctua as far as good 120mm fans go. Heck, if you really wanted to, you could add in multiple side panel fans which would be akin to the likes of a Cooler Master Stacker.
I know its frustrating, but please refrain from letting it get the best of you. We're all trying to help here and we really don't have to if we don't want to. So show a bit of appreciation or just don't say anything. As far as everything else goes, we can't read your mind or envision the state of your setup or anything like that, especially without pictures. We aren't super heroes or psychics, we don't know what you know. I'd imagine that's why Eck posted what he did. Not to be patronizing, but simply because he doesn't know what you know. You can't blame him for that, can you? Also, its wise to be kind to the moderators.
Best of luck, hope you figure this problem out.