I have used 4xAA rechargeble batterys before, measured at about 5,5v, and did not have any problems with that so far
i even use them to connect through the arduino connector, but passing through the on board regulator means you lose about 1 volt (tested on my mega1280)
hope this helps