В начале EEPROM создать таблицу, в которой хранить номер-идентификатор (если он нужен), смещение в памяти (чтобы не складывать все размеры при поиске), размер записи. Дальше размещать сами записи.
При стирании перемещать записи на свободное место, корректировать номер и смещение.
ЗЫ. Таблицу разместить в конце памяти, и чтобы она росла к началу памяти. Тогда можно забить память до последнего байта...

ЗЗЫ. Номер не нужен, он однозначно определяется местом в таблице (или нет?).