Options for semi-permanent memory in a low-energy setting
Some of TI's MSP430 microcontrollers provide persistent storage in FRAM, which has some very interesting characteristics:


It's non-volatile - no power is required for data retention.
Fast read and write times (TI claims 50 ns)
High endurance (TI, again, claims 10^15 cycles)


(The numbers I'm quoting are from TI's FRAM FAQ.)

Of course, this is only useful to you if the MSP430 is an option — it's not available as a standalone part at this time.