What you describe is typical of EEPROM chips. The minimum number of bytes you have to erase at once, the maximum you can write at once, and the minimum you can write at once can all be different.
The way I usually deal with this is to have a module that virtualizes reads and writes to the EEPROM. This module presents a procedural interface for reading and writing individual bytes.
By the way, it's a good idea to have this module use a wider address than what the EEPROM actually requires. It's not uncommon at all for projects to evolve and replace the EEPROM chip with a bigger one later. If you only used a 16 bit address and went from 64 kB to a larger EEPROM, you have to check and possibly rewrite a bunch of app code that now has to use at least 3 address bytes when it was written for 2. Usually I use 24 bit addresses on a 8 bit machine and 32 bit addresses on a 16 bit machine to start with, unless there is a good project-specific reason not to. That also allows you to create modules for various different EEPROMs that all present the same procedural single-byte read/write interface. Sometimes I have build-time constants that create short-address versions of these routines when the EEPROM size allows it and when taking the risk in the app code is worth it.
Anyway, the EEPROM module maintains a RAM buffer of one erase page (those are usually larger than or the same size as write pages). The module keeps track of which EEPROM block, if any, is currently in the RAM buffer, and whether any changes have been made (dirty flag) that have not yet been written to the physical EEPROM. App reads and writes work on this RAM buffer and don't necessarily cause read/write directly to the EEPROM. A FLUSH routine is provided so that the app can force any cached data to be written to the EEPROM. In a few cases I used a timer to call the flush routine automatically some fixed time after the last write.
When the app accesses a byte not in the RAM buffer, then the block containing the byte is read from the EEPROM first. If the buffer is dirty, then it is always flushed before a different EEPROM block is written to it.
This scheme is generally faster, and also minimizes the actual number of writes to the EEPROM. The dirty flag is only set if the new data is different from the old data. If the app writes the same data multiple times, the EEPROM is written to at most once.
This scheme also uses the EEPROM more efficiently since entire blocks are erased and written at a time. This is done once per block regardless of how much write activity there was within the block before the app addressed a byte in a different block. For most EEPROMs, writing a whole block or writing one byte within a block count the same in terms of lifetime. To maximize EEPROM lifetime, you want to write as infrequently as possible, and erase and write whole blocks when you do.
Best Answer
1) Use a forward error correction system which offers to recover from multiple missing bits. Distribute the FEC data across different blocks in the EEPROM.
2) Keep at least two whole separate copies to allow re-writing.
2) Periodically re-read and check for any bit errors. Re-write damaged bits. If they don't re-write cleanly, report an error (how? to whom?)
4) Pay huge attention to your board design and part selection; watch out for rotting capacitors etc.
5) You might want to consider "single event upset" (SEU) rates in the processor: while this is normally only a consideration for aerospace, you're running the thing for much longer.
EEPROMS are floating charge devices. They do leak over time, so I think the retention is from the most recent write cycle.