SOFTWARE TYPES:
There is a race condition involving the EEPROM unlock circuit. This can be
cured with a very simple software change. See your hardware guy to see if this
is a problem with your hardware. 

HARDWARE TYPES:
A typical EEPROM lock circuit is shown below:

      /UNLOCK ____                                    
                 |                                
             +---o---+                           
             |   S   |                             
       GND --|D     Q|---- /OE                               
             |       |                             
             |       |                             
       /WL --|>      |                               
             |       |                             
             +-------+                           

The problem is that /UNLOCK and /WL occur at the same time, plus or minus a
gate delay or two. If the path for /WL is slightly slower, the EEPROM will not
get unlocked. The solution is to do the unlock with a byte write to the high
byte only. This suppresses /WL and the problem goes away.