Hi Thomas,

"... output high voltage can be -0.6 to VCC+0.6."

Ehm, no, that's from the absolute maximum ratings section and has little to do with the normal operating conditions. The "DC Characteristics" section says that the minimum Voh (output high voltage) is Vcc-0.2V when sourcing 100µA.

Let's assume that the regulator you are going to use has a tolerance on the output voltage of 5% (that's a reasonable assumption; most 3.3V regulators are even better at 2%). That means the minimum Vcc will be 3.135V and that the minimum Voh of your Flash device will be 2.935V. At the worst case Vcc of 5.5V for the micro, this gives you a noise margin of around 0.9V, which is plenty.
The maximum Vol (output low voltage) of the Flash is 0.4V, while the maximum Vil (input low voltage) for the micro is said to be 0.2*Vcc-0.1V, which equals 0.8V at Vcc=4.5V (worst case).
From this we can conclude that this is a reliable setup.

I hope that this gives you some idea of the things to look out for when designing mixed-voltage systems. If not, feel free to ask more :o)

Best regards,
Rob.