It doesn't have to be a linear regulator.
One example suggested on an electronics forum was an ICL7660 switched
capacitor regulator which apparently can be better than 99% efficient for low-power supplies.

Sounds better than a 7805 to power a battery monitor
(ie. I don't want a battery monitor to chew up much of it's own power).

The current I'm talking about I don't know exactly, but it's a 16F876, I2C EEPROM, and 2x16 LCD display.
Surely that is a low power circuit. I might even be able to sleep the chip when I'm currently pausing.
Art.