we had this same issue a few years ago - we settled on one brand of replaceable batteries - we went with energizers which we switch out right before every run during the tournament.
One reason is that the discharge curve drops off pretty severely after a short while - also the rechargeable batteries have less and less staying capacity as we go along.
We also run the robot a few times through its program set before the competition round - takes the edge off the discharge curve. Here's the AA discharge curve that backs up my thinking: