Many on the patterns at,24c256 and at24,24c256 (should be probably
be atmel,24c256)

I remember patches fixing that. Since I usually don't take DTS patches,
I can't recall what happened to them. It might well be that those were
accepted and meanwhile new bad bindings got in.

but also a few atmel,at24c16 and atmel,at24c128b.
I don't understand how those last ones ever worked, if it is not
working for you? Especially those with the trailing "b". WTF?

I'd simply assume it was never tested. EEPROMs are often convenience
storage and not essential for a working board. Also, for historic
reasons, they are often used via the i2c-dev interface directly, so a
wrong binding with the kernel driver might simply go unnoticed.