I would power the servos separately from the Arduino ouput. Why put all that stress on the board if you don't have to? The regulator will already be warm from dropping 7.4V or 11.1V down to 5V.
I wouldn't count on the 800 without looking up the regulator on your board.
For instance, on my Duemilanove the regulator is marked
1117M3
500952L
C249694
and the body is visibly different than what can be seen on the current Uno's.
I have been trying to figure out what part of that is the part # so I could look it up.
Nothing looks like MC33269D-5.0 that is on the Deumilanove schematic.
I am thinking it is this
in the smaller SOT-223 package.