Put it this way. On my old amd athlon 2800+ I didnt clean the fan and heat sink for about 4 months.
I was getting idle temps of 55-60 degrees C.
I cleaned it and it drop to 35-40 at idle.
Your best bet is make sure you clean it completely once a month. PSU is a big attractor of dust, as is HSF for the cpu, the capacitors near the northbridge, the northbride itself.
Inbetween all expansion slots, HDD, Optical drives. and all the air intakes and outlets.
A clean system is a healthy system.