You can easily check this with your finger tip: The 5V regulator is either located next to Vcc pin or ground pin, when a DIL-package is used. As heat transfer into the DIL-package is provided by the internal pinning frame (internal connections from pins to die), the package must become hot asymetrically, means the package must be hottest at the pin, where the regulator is sitting next.
If the micro itself produces the heat, then you should notice the hottest point exactly in the middle of package, just where the die is sitting under the surface.

Limitations of loading of port outputs is not so much in order to prevent chip from overheating, but to prevent the signals to loose TTL-compatibility. When a maximum IOL of 71mA is allowed for the whole of 4 x 8 port outputs, then this means an average current of 2.2mA per pin. With these currents VOL is in danger to rise much above 0.4V, which violates TTL-compatibility. Power consumption due to voltage drops of these port output currents is rather low, on the other hand: Even if we assume VOL = 1V, which is much higher than we would observe, then only 71mA x 1V = 71mW would additionally heat up the package. This is enough to heat up a tiny 0603-SMD-resistor, but is not at all enough to give your huge 40-pin DIL-package the temperature rise you observed!

Kai