We needed to build a way of storing small amounts of data very quickly with persistence across a restart. Because Flash is relatively slow and the whole write-cycle life issue we ended up creating a shield using I2C F-Ram (FM24CL16B-G, <$1.50 from Mouser) for 2KB of storage. Because of the nature of the ram it is very simple and lightweight and works perfectly for what we are using it for. We would love to split the cost of turning these into production boards if anyone else is interested. Let me know!
Correct, Arduino form factor (using Cerbuino). Both factors entered into choosing the chip we used. We are storing pulse counts so possibly very frequent updates for very small data - would have quickly killed Flash storage. We are using to store a few configuration parameters as well. When we detect a flash insertion we copy the configuration from the flash to the F-RAM so you can quickly copy the config across several devices with just one SD card. They do make bigger F-RAM chips, a 1Mbit (128Kbyte) chip goes for about $11 - they will work with our shield as well just different I2C addressing.
We also put a 24 pin IDC header on the board so we could ribbon cable it to a custom opto I/O board for higher voltage inputs/outputs.