Some of the Lutrons I have had the same problem with. The aluminum fins on the side that are so difficult to fit into a multi-ganged box, and that you'll be tempted to break off to accomodate multiple devices in a box, lower the wattage rating when removed. I think I remeber the manufacturer telling me that you loose 100Watts capacity or more per side when you remove these fins.
Even with the fins intact, I have had to explain to a few clients that sometimes the dimmers just run hot when you have anything more than 350-400W running through them. I've even replaced a particular unit several times, and the heat factor remained the same (this one was a 600W unit passing 450W on full load).
If it's not a Lutron device or similar, I suggest you contact the manufacturer using the 1-800 number on the box or through their web site. They may have some tips on reducing the heat output on their particular model.