AA??? I'd guess AAA at that capacity, not AA.
They must be very old. If so, I'd guess they have lost much of that rated capacity due to aging.
Yep -- AAA has much less capacity than AA. NiMH would give you much higher capacity (up to 1000 mAh), and thus longer life, even with the higher self-discharge, and even assuming your NiCd are fully up to snuff.
I'm skeptical. Most such devices, including the old Logitech Cordless Wheel Mouse I used to own, are designed to tolerate a wide range of battery voltage, and only complain when the voltage drops below about 1.0V. While NiCd and NiMH have a lower starting voltage than alkaline, they have a very flat discharge curve as compared to the discharge slope of alkaline, and usually give proper life in digital devices. I can only think of one device where this isn't true, a very old cheap digital camera where the built-in flash was the likely culprit.
I'd be willing to bet that the best NiMH AAA would give you at least 50% more runtime than your NiCd AAA even with higher self-discharge.