I believe there's a simple way to use only n cells and a single dedicated bit pattern to achieve n/2 increase in durability.
The dedicated bit pattern (e.g. 0xffff) is a marker which indicates an unused cell, and in normal operation at most one cell at a time has this value:
uint16_t readWord (const uint16_t *address);
void writeWord (uint16_t *address, ...