Bryan,

   I'm not sure if this will work in your situation, but Ramtron
International Corp. makes a serial (i2c) non-volatile memory that can
handle one or two orders of magnitude greater write cycles than
EEPROMs.  Right now, 4Kbit (FM24C04) is available.  It also can be
written to on the fly--just like the EEPROM (except no charge-pump).

This really isn't an ad, but I thought you might find it useful for
your application.

For more info, e-mail to me:

Greg Smith
Design Engineer, Ramtron Int'l Corp.
greg@ramtron.com

BTW, someone here created an "EEPROM killer" board using 2 PICs.  It
destroys (with multiple writes to the same location) competitor's
serial EEPROMs in about 7 minutes.  Rough calculations show that our
FM24C04 will last approx 56 days even considering that the EEPROMS take
multiple msecs to write, while our writes are hidden in one 400KHz
clock cycle (we haven't yet killed one of ours).