FYI, I was just looking at a C3000 p2rom:
The table of supported NAND chips starts at offset 0x1c4a0.
Supported are:
Toshiba TC58512FT (Maker 0x98, Device 0x76, 64MByte)
Toshiba TC58DVG02AFT (Maker 0x98, Device 0x79, 128MByte)
Samsung K9F1208U0M (Maker 0xec, Device 0x76, 64MByte)
Samsung K9K1G08U0M (Maker 0xec, Device 0x79, 128MByte)
Samsung K9F2808U0C (Maker 0xec, Device 0x73, 16MByte)
Samsung K9F5608U0C (Maker 0xec, Device 0x75, 32MByte)
Erase size 0x4000, block size 0x200, oob size 0x10 for all of them.
Another value (bank size?) is 0x4000000 for all of them except the Maker 0xec Device 0x76, where it is 0x8000000.
In theory any chip that has the right Maker/Device and matching parameters and is command set compatible should work.
I'd try looking at 128MB or 256MB usb sticks or 256MB/512MB CF cards for matching parts (My old 64MB usb stick uses a TC58512FT compatible TC58DVM92A1FT 64MByte TSOP48, but the sticks PCB has room for two chips).
HTH