Hi,
I don't really see the point of linear regulator. A 5V one, LDO or normal, will drop out of regulation pretty quick, then it behaves as if it wasn't there in first place - or worse. Using a lower voltage like 3.3V or 2.5V will only turn useful energy into heat in the regulator so that's no good either.

The "best" way would of course be a switching type boost/buck converter/regulator so that the PIC can be fed 2.5V (or whatever) from "any" supply voltage, the good thing about this is that the PIC Draws much less current at lower supply voltages so provided the converter/regulator is efficient you'd get more use out of the batteries. But, it adds complexity so.....perhaps use 3 cells in series instead of 4.

/Henrik.