Wow! There are a lot of great advices there!!!
Thanks everyone!
So let's make a quick checklist
(1) I should remove the 7805 regulator
-One alternative is to remove it completely and run the circuit directly from the batteries. Diver300, you said that I should run it with 3 instead of 4 cells. However, the batteries peak at 5.6V (thanks philba for the great link!) which is within the limits of the PIC. Unfortunately I dont have an LF here.
-The second alternative is to use a switching regulator. I did not know about these so its a good thing to learn!
(2) I should do something about MAX202
-Thanks Nigel! Indeed MAX202 needs 3~8mA so I could use the PIC pin for sourcing current.
-As Mike suggested I could use MOSFETs to level shift the voltage (thanks! MAX202 costs!). I googled for 'MOSFET level shift' but could not find something quick. If you have a link it would be nice!
(3) Clock frequency:
-Mike suggested to remove the crystal oscillator and use the internal oscillator. Now why didn't I think that???
-Nigel suggested to reduce the clock frequency. I dont think I can do this for this project but I will add it to my library of good practice!
(4) PIC sleep:
-As Nigel suggested I could do multiple short sleeps which will add up to the long one. Actually I thought of that (hooray!) but I was wondering if I could make it with one sleep only (or two!)
-Mike, I hadn't had the time to look at the ULPWU devices you suggested but it sounds like is what I am looking for!
I am using forums for many years now but I never had any GOLD advices in one place like this thread!!!! Thanks again guys! I will try few things and I will let you know how it went.