iirc 'normal' rechargeable NiMH AA batts are rated at ~1850mAH. There are now various similar batteries available from 2300-3100mAH, so that's roughly a 50% gain in runtime.
I've had good results with Panasonic eneloops, but they are 2100mAH, still better than a regular AA battery. And they are working fine in a wide range of devices for me, including a Garmin Legend C handheld. better yet, they work great in a small 'solar wallet' contraption I have, which also works to recharge USB devices.