Ramtron makes a very fast FRAM that's pinned out similarly to an SRAM I use. It's 256k x 16 bits, but is also available as 512k x 8. That would allow you to store a very large amount of data, yet access different windows depending on your requirements. Further, the RAMTRON part has none of the delay requirements that most FLASH parts have, as its read and write cycles are just like SRAM.

I'm not sure this will solve your problems, but it is an option, and, of course, if you're pressed for time you can do things WAY faster than with serial memory. Another thing to keep in mind is that you can externally register output port bits at the start of ALE, so as to avoid interruptions to your external devices, when you're using the externally expanded memory bus.

RE