Have you considered running your ooPIC at lower then 5V? Looking at the datasheets from some of my PICMicro MCU's they can operate from 2V to 5.5V - not strictly 5V; You probably need a fixed 5V supply while programming them but that's it! I'm not sure how this would affect other aspects of the MCU operation, like oscillator stability or ability to run at maximum oscillator speed but an compromise can be made.
Back to your issue. Since you're going to run off 4xAA batteries, you're going to have a maximum of 6V (4x1.5V for alkaline primary cells) or 4.8V (for a pack of 4 NiMh cells).
About the minimum volts in those cells: I had a hard time locating some battery datasheets that would give exact numbers. I found something like this in a Duracel datasheet (alkaline AA):
If the battery voltage is greater than or equal to 1.1 volts, the battery has approximately 20% service left;
NiMh cells can apparently discharge all the way to 0V - but it's not safe to do so, one's supposed to stop discharging at 0.9-1.1V in order to keep the cells from being damaged (when one cell in the pack reaches 0V and the others still have some power left in them). So the practical minimum for both types of batteries would be around 1V per cell, 4V per pack.
So you want a power regulation solution that can feed your electronics from a power supply of 4V to 6V. I'd suggest a LDO linear voltage regulator with "voltage following" capability (so the regulator would feed your electronics whatever it gets from the batteries when the voltage drops under 5V). Or no regulator at all! If someone loads 4 fresh alkaline batteries in the car the voltage will be over the maximum 5.5V accepted by the PIC but not for a long time: once the electric motors in the car start spinning I'm pretty sure there will be a drop in voltage!
