1) Are there any PIC chips with 4KB of EEPROM available?
2) I tried, can't make it work.
3) Also does not work.
4) Running on PIC16F887, code is already tight
5) No open source hardware/software in my projects ever
6) Actually they do work fine.

And regarding the DS28EC20, if you noted, topic reads "DS28EC20 and similar" This means, that in case of need, say, DS2505 can be used, which has 64k.