You can certainly get low power consumption 5V regulators, but if running off batteries you would probably be better to use direct battery power and no regulator - three 1.5V cells in series power PIC circuits quite nicely. Four Nicads (or NiMh) are even better.
He needs a low quiescent current, not a low dropout.
There's the LP2954 reg with 90uA quiescent current, expensive though, about $4 from Digikey, it also only guarantees 250mA of output current. But it is 1.2% accurate over the entire temp range, very high precision.
Search through Digikey, "low quiescent current", "low power", "low standby current". There are some other entries in their filter menu for "ultra low (insert property here)".