In my fluid dynamics class... I put the myth of opening the sides of the computer cooled it faster to the test. You are correct Ro.
I found that once one side of the case was removed, there was little airflow moving past the critical parts like the CPU and various cards. The only true way to increase cooling, when removing the side, would be to place a large room fan pointing into the case. Either that or use water cooling
As for the problem at hand... make sure all filters in the computer are free of dust (if it came with some). If they clog, they will inhibit airflow. Another problem is dust build up on the components, which you have already solved.
Are you sure the CPU fan is working? It may spin, but it might not be spinning fast enough. Also, touch the heatsink for the CPU and see if it is really really hot. Do the same for your graphics card (Warning: Touch the power supply case with the PC plugged in before touching any components).
Does it overheat at specific times? Like when you are watching tv or playing games? Or is it random and doesn't matter what you are doing on the PC. Also, how much time does it take to overheat?