Your thermal paste spreading story MAY mean you have too much on. It's not always recognized that too much thermal paste is almost as bad as too little. You always need some of this material to fill in the microscopic air gaps between heatsink and CPU, but the paste film also acts as an insulating layer because it does slow down heat transfer a bit (although not as badly as plain air). So the idea is to apply as thin as possible of a film so that the air gaps are filled, but not much more. When you apply a "pea sized" amount and spread with a credit card, that may be too much. If you go to the Arctic Silver website you'll find their instructions. On my CPU (don't know on yours) their instructions were to apply paste about the size of one to two grains of rice (smaller than a pea) and then seat the heatsink on the CPU, giving is small twists in both directions to spread the paste, and finally fasten it down. So you MIGHT consider removing the cooler/heatsink, cleaning off the paste as best you can (if it's reasonably fresh you probably will not need extensive cleaning with solvents) and re-applying according to what you find at the AS website.
I'm going to disagree with LenoxLV somewhat. The total air flow through the case really is not changed by whether the case is under net positive or negative pressure. Actually, the ideal is to be almost balanced between intake and exhaust flow rates. Personally, I prefer a small net positive pressure inside, but NOT for flow rate considerations. In my way of thinking, you can (REALLY should) place air filters on the intake fans to prevent entry of room dust. If you do that AND arrange for a net positive pressure inside the case, there will be outflow of air at the leakage points and that will prevent sucking in uncontrolled dust.
One way to check, although not very precise, was pointed out in a post some time ago on this topic. Light an incense stick or something like that to create a small smoke plume generator. Move this around the case and watch where the smoke goes. If it flows slowly away from the case at leakage points, you have a slight positive pressure inside. If the air flow at those points really blows the smoke away, you're probably too positive inside and could try to re-balance. NOTE that, because of the intake filters and air flow restrictions, you cannot estimate an air flow balance simply from the fan specifications.
A couple more thoughts for you from my experience.
My computer desk has an open pedestal or "cubbyhole" under the top for the computer. It was designed with no fromt door but the back opening completely closed off by a panel nailed on. That panel helps with maintaining the structural rigidity of the desk, but it completely blocks off all air flow behind the computer. So I never installed it. Instead I found a wire mesh or grid I thought stiff enough and fastened it on with screws so there is free air flow back there.
Recently I was tracking down what I thought was an overheating problem. (It became apparent a week later it was really a PSU going bad.) In the course of cleaning out air filters and dust which involved moving the computer around, I realized that the CPU and case temps actually had gone up! I reached to the back of the unit and confirmed that the movement had piled up a bunch of cables behind the case, right where the air intake grille for the CPU was. Moving them away dropped the temps by several degrees. Moral: always look for things in the air flow path that are restricting the air - inside the case or outside.