This sounds like the behavior of RAM not EEPROM. I am also curious if the EEPROM is actually getting data. I know that there is some funny unlock sequence for it accept writes as mentioned earlier. However I am not sure why that would cause it to magically record and return the correct values after a certain amount of time but not write it to memory. I mean its possible its cached, but if I remember correctly that is not how it is implemented. Also the correct value would be returned immediately or no more than the EEPROM page delay. Part of me says bad chip, but that does not sound likely either.
How do you know the data is right? How do you know that the data from the previous run is persisting a power cycle? (You have to suspend writes to test this!) How large is the window before the data gets overwritten?
Can you burn into the EEPROM a string like "Hello World!" with one program. Then try to read it and see if you can see it? Suspend all the other logic so that this is the only thing using the EEPROM in both programs.