Well, if you don't mind getting into Li-Ions, the 18500 size is pretty common in solar lights. I was able to get some LiFePO4s from Wal Mart for about a buck each. These 3.2v nominal cells require a different charger from 3.6/3.7v nominal cells, but they have acceptable energy density. They'll fit with a bit of rattling in place of a 3xAAA carrier, and can be more firmly held with a spacer or something.
If you don't want to go to Li-Ions, you may want to try quality NiMHs. You'll need to get a somewhat-select charger though, since a sickening number of NiMH chargers only want to charge pairs - this is annoying when you use in threes and charge in twos.