Xicor first suggested the x20c04 as a replacement for the x22c12 (but not a drop-in replacement), then they discontinued that part without any suggested replacement. Xicor was bought by Intersil some time ago. Now they're interested in EEpots, and in larger nonvolatile memory, which they call Alterable EEPROMs. Their x28hc64 is the smallest part, with 8k-bytes in a 28-pin package.
Seiko and Catalyst make nonvolatile memory, and had parts similar to the old Xicor parts (e.g., Seiko's 22h12 and Catalyst's 22c12), but they've been discontinued. Catalyst still offers a smaller nonvolatile memory, the cat22c10, which is 64x4. Go figure.
Sorry, Simon.