Der Stromkonsum hängt im wesentlichen von der Taktrate eines MCUs ab (linear) und quadratisch mit der Versorungsspannung. Folglich, Takt runter, Spannung runter und alle unnötige Peripherie abschalten und wenn der Controller nicht gebraucht wird: Schlafen legen.
Als Spannungsregler einen "Low Quiscience Current" Typen nehmen. Dann dürftest du auf wenige µA kommen.

Solltest du den ganzen Schmarn nicht machen wollen, dann dürfte ein MCU auf 500µA (0.5mA) (typisch bei Atmel) pro MHz kommen + Perifiere. Bei PICs kenne ich mich nicht aus.
Achtung: Wenn du den 7805 oder so als Spannungsregler verwendest, schluckt der alleine schon 5mA.