I tried the following:

wrote first to the 7FFFh address (which happens to be RAM, then wrote to 8000h (which is 000h in the EEPROM). The problem still persists...

However, it seems that the value written at the beginning address (I tried a new chip) is 5Ah, (always). The spec sheet for the AT28C64 says that the data is written in the same manner as to a SRAM: address is latched on the falling edge of -WE, while data is latched on the rising edge. Still, this does not explain the problem with the first address in the EEPROM.