are you sure the eeprom contents are preserved when a new sketch is uploaded?
according to boards.txt file for UNO, the fuse settings are (low, high and extended fuse)
0xFF 0xDE 0x05
and if you enter those numbers in
http://www.engbedded.com/fusecalc/
for atmega328p
it shows preserve eeprom memory through chip erase cycle as disabled.
If I check that box, the fuse setting is changed to
0xFF 0xD6 0xFD
the extended fuse value of 0xFD is equivalent to 0x05, so the only thing that changed is the EESAVE value of high fuse.
same for atmega2560
boards.txt fuse setting says
0xFF 0xD8 0xFD
if I check preserve eeprom, the fuse settings change to
0xFF 0xD0 0xFD
if you have another uno or mega, you can use arduino as isp sketch to change the fuse setting. just change the value in boards.txt and burn the bootloader on the target. if you want to get a programmer, you can get a usbasp for under $4 on ebay.