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

The MODE pin is for types with a 'w' and older types.
So your chip might have that mode pin, but I'm not sure.

I didn't look into the Mode and pages. I was hoping that reading and writing a single byte per I2C is enough for you.

The 24C04 should have 9 address bits for the register address (A0...A8).
The address byte is 8 bits (A0...A7), so where is the missing 9th bit ?
I searched the datasheet for A8, and it is in the I2C address !
That is why you have a memory at 0x50 of 256 byte, and another memory at 0x51 also of 256 byte. Both the 0x50 and the 0x51 device are in the same 24C04.
That is how they did it.