...The crazy thing is the old EEPROM works when the machine is on for a while/warmed up...
That sounds like a possible cold solder joint issue or a defective chip.
Run a solder gun on the pins from underbeath just enough to reflow.
An 24C04 EEPROM lasts long but doesn't last forever.
Its lifetime expectancy is about a million writes, and that the chip gets written to at about every 100 games played.
I doubt your game has been played that much
It sure sounds more like a defective chip problem more than anything else.
That thing is well...old as dirt? lol

I'd cut the legs off above the surface of the circuit board, unsolder the pins and solder in a new chip.
UPDATE
I see you've put in socket!
Good job!
Check out this sheet...you'll see the specs on it...>>>