Try taking a larger gauge wire and jumpering VCC and VSS to the other side of the board (near where the v-drop is largest); if you see the voltage drop go away or decrease significantly the power distribution raids on the PCB may be too narrow (you end up with higher series resistance in the PCB traces); thinner copper will have higher resistance as well. If I'm remembering correctly sheet resistance rules apply to copper as well as thin films. http://en.wikipedia.org/wiki/Sheet_resistance
I'm also seeing TO220 NOS 7805s that are way out of spec; these tend to be generically marked (no brand name) and have been between 4.7 to 5.2 VDC for me.
-Neil