Just my suggestions - been a while since I worked on systems but....
Multiple monitors and heavy apps shouldn't effect the power supply to much since it will still only draw what it is built to draw. Being underpowered (as I recall ) will not damage the system but will cause malfunctioning from components not getting enough power.
I think the key here is the clogged power supply. If it can't cool itself then it will be toast pretty fast. Just the same with all other components - the heat is going to be the biggest problem. All the components produce heat a layer of dust is like a blanket to help hold it in.
I think cleaning every 6 to 12 months should be fine. Hard apps and more monitors do not mean more dust sucking up into the computer. I don't know how your computers are placed but on the floor are a bad idea they will collect dust much faster. Better to have them in a cabinet.
Are the office staff normally allowed to open the computers up?