Thermal images of a Mega

focalist:
I would think that in some ways this is a superior power solution than using the onboard regulator, but the nagging question remains in my mind as to whether the traces to the leads on the board are okay with this method of providing power, and if there is any issues I hadn't otherwise considered?

I don't see why that wouldn't be a good solution (always use the caps, though - it prevents oscillation of the regulator); in fact, it might be better, since you could add your own heatsink, or (if you wanted), add a bypass transistor to bump up the current output.