Erik,
I have same problem once. So as for now I do next:
1) split flash memory on regions depend on how much memory I need for a record(s). Usually they are flash sectors (for sector-based flash) or just equal parts (for byte-erase/write flash).
2) define BASE POINTER address (one or two bytes) somewhere in flash memory (I preffer 0x0000 :). It always shows on the current active region.
3) Now I need write. It depends on flash organization - should I erase sector before operate or not; anyway, for example:
- follow BASE POINTER and determine which region is used. Either erase sector or read byte and compare with one is needed to be written. If it is the same then pass it and go to next byte. If different then make write operation.
- important: check value was programmed. If it fails then I preffer to do yet another extra write cycle. Anyway: if it is (permanent) error then I fall back to the base pointer and increase it to next region. Then repeat all the things for new flash region. If base pointer has counted last free region then software reports about hardware failure: flash resource was exhaust.
By this way it is possible to multiple flash limit cycles on number of regions.
Btw, I preffer:
- AMD as flash memory vendor - usualy they guarantee 1.000.000 write cycles;
- for small data/quick access holder: FRAM from Ramtron (use FM1808: 32kbytes Ferroelectric Nonvolatile RAM - 10 Billion(!!!) read/write cycles; 10 years retention without a 3.3 battery);
- for each-second-write and big enough space: Samsung SRAM with 3.3 battery (here I use K6x4008 series).

Good days!