If you Format/Erase your EEPROM to say all $FF, by simple Binary Division you'll be able to determine your last used location in 1Mb of EEPROM using about 20 reads or less. Since reading is near instantaneous and doesn't wear out the EEPROM, even with rubbish code you'll get your answer in under a millisecond.