as time goes on, technology improves
what that means is...
the replacement cells you buy are probably going to be the same mAh or better than the originals
(assuming the same size, shape, and mass)
it's really hard to go wrong, in terms of capacity
if you buy "less", the thing simply won't hold a charge for as long
if you buy "more", it may take a bit longer to fully charge, but will run longer
what i would look for are cells that have soldering tabs welded on :t
i think what you want are standard "AA" cells, which probably ran ~500 mAh at the time of manufacture
you can replace them with longer-life cells
these look nice...
http://www.parts-express.com/pe/showdetl.cfm?partnumber=140-184