You do have to keep the heatsink and fan clean. If they get dust and dirt on them the temps will rise. I smoke like an old frieght train and have to clean mine on a regular basis.
Having said that the real trick to cooling is not how many fans and where they are on the case but to balancing the air flow. Figure on doing a total exchange of the air in the case on a per second basis. Again I'm not going to type all that in on how to do it but just refer you to some builds I did that explain all that.
Pay attention to page 3 as it has the formulas for figuring out what fans you need.