Arduino Regulator: How hot is too hot?

One thing you may want to considder is what voltage are you putting in?

If the board runs on... say 5 volts. And you are putting in..... say 30 volts. The board is needing 2 amps to work.

That is a lot of "EXTRA ENERGY" which needs to be dissipated somewhere/how.

If you supply it with 6 volts, there would be a lot less heat generated on the regulators.

Just a thought.