I've just modded my PC case - the Antec 900 by cutting holes in it for cable management. I bought the holesaw kit off the 'bay for £3 plus postage!
You'd need that, a couple of 80mm fans and fan guards (£6-£7 each) and you'd want a small metal drillbit for the screw holes for the fans. Could do it for under £20.
It's not as hard as it sounds, though a little daunting maybe. Taking a drill to a new case just doesn't seem right, that's for sure, and my case was £70!
If you do go down this route, alls you need to do is cut 1 big hole for each fan and 4 holes for the screws to mount the fan, slap the fan in the case, fanguard on the outside and mount with the screws. Trick with the holesaw kit is to dril slow and steady - can take 15 mins to drill 1 hole. You don't wanna be pushing too hard or you risk bending the case, which aint good.
You can get diamond edge holesaw kits but needless to say they're more expensive.
It must be an airflow issue here. You have remounted your TT with new paste and its still warm, so can't think it to be anything else. This will be the cheapest solution for you - to mod rather than buying a new case. Invest in some cable ties too and try to make all cables as neat and tidy as possible, hiding them wherever you can.
Hope this helps mate.