Why am I having so much trouble working with I2C EEPROMs?

They are open drain when I2C mode is enabled. The standard arduino I2C library enables 'weak' pull-ups to the boards Vcc voltage for the two I2C control signals, something like 40K ohms.

Well that would explain it.