So, if I follow your logic, I should write in a trailing "available" value that I shall overwrite and push forward as I go. Then, at boot time, I scan the EEPROM for that value and remember where I saw it, so I can increment from here. If I can't see it anywhere, I filled up the memory, so I start over from cell #0. Is that it?
However, when you say
since 0x0000 and 0xFFFF are both within range, do you suggest that I should first initialise the whole memory? At this point, doesn't it make more sense to just stop as soon as I see the first "available"? This would tell me that the last 2 cells I wrote to were the ones just before.