Personally I'd toss the AAA battery mouse for one that takes AA batteries. You get about 3x more energy in a AA battery compared to AAA which makes them much more convenient for a mouse.
A NiCD AAA will give you 300mAh of power. NiMH will do 800mAh on the low end, some brands proclaim up to 1000 mAh. And, yes, NiMH self discharges at a higher rate but you're starting with 3x the power. So if NiCD is 10% a month and NiMH is 30% a month you end up with something like this:
NiCd 0 months: 300
NiMH 0 months: 900
NiCd 1 months: 270
NiMH 1 months: 630
NiCd 2 months: 243
NiMH 2 months: 441
Yeah, NiCd doesn't really come out on top here. Not even when idle. When you're actually using something NiMH wins out handily.
Plus there are LSD (Low self discharge) NiMH batteries out there that only give of 2% per month. I don't use many of them, but it's true, they really do work. You give up a bit in peak capacity, so I tend to keep them around for flashlights, not my XBOX controller, but they are nice. You'll see the LSD stuff labeled as "pre charged" usually. Marketing weirdo stuff. I guess people hate getting cells that only put out 1.1 volts upon arrival and need a charger to become operational. Makes sense from a marketing perspective but the labeling is confusing to people that just want a good LSD battery.
A good charger will do a lot to keep your batteries in good condition. Cheap chargers ($10) that require a pair of batteries to actually do anything measure voltage across the two and don't cut off the charge current until they hit 3.0V-ish combined. That means if you put in a pair with one semi-charged and one darned near dead it heats up the better battery too far. It's still handy to have one around, though, because they're cheap and they'll keep 2-4 batteries topped of nicely.
My favorite chargers are the BC series from La Crosse. I have the BC-700, but the BC-9009 is as good, if not better. It charges cells one at a time. The BC-700 will put up to 700 mAh back into a battery and the 9009 will do 900 mAh. Both are pretty safe if you're dealing with AA batteries. I like to keep my AAA cells charging at 500mAh. The BC series lets you pick the charge rate.
Unfortunately if you let a battery go REALLY dead the BC series won't do anything. It detects battery presence based on voltage so if I shove a totally dead one in there I'm screwed. I just toss it into a cheap dual-charger with a decent battery and let that ramp it back up to normal voltage. But, given that I have the BC charger which will tell me current voltage I can figure out which batteries are also close to darned near dead and I can pair that with a dead one before sticking it in the dumber charger. That prevents overheating. Overheating reduces battery life.
And for cheap, but good, cells I'd recommend
http://batteryspace.com ... their 'Tenergy' brand has done me well. For LSD I'd say hit Amazon and pick up GP Recyko branded stuff. And if you want a charger they've got great prices on the La Crosse stuff there too. Unfortunately the Targus branded wall-wart that I use for brute forcing batteries back to health is no longer on Amazon. I got it for $10 and it came with 4 2500mAh AA batteries. It was a steal.