The AT45DB081D dataflash memory holds over 8 Mbit, organized as 4096 pages of 256 (or 264) bytes. It’s easy to connect to a JeeNode:
Looks a bit messy at close-up but it’s actually quite sturdy with 6 wire-wrap wires.
It’s quite easy to talk to this device. Here’s the sample output of reading and writing 100 blocks:
It looks like reading takes about 1.1 msec per block and writing 8.6 msec. A scan over all 4096 blocks while reading only 8 bytes from each takes less than half a second, so it’s definitely feasible to scan the full memory when starting up.