Your idea that "no air would be able to enter the nozzle because the vehicle is moving faster than the speed at which air would be sucked in" is inaccurate. But the vehicle speed is irrelevant here.
The answer is pretty well-summarized in the top answer here as someone else linked, but to re-state it:
Vacuum-optimized engines are not operated in the atmosphere because of flow separation in the nozzle, which leads to large side loads (against the walls of the nozzle) and instabilities in the nozzle, likely leading to structural failure or collapse of the nozzle. Flow separation can also generate shocks inside the nozzle, which will also lead to structural failure.
Flow separation occurs when the pressure at the exit of the nozzle is significantly lower than the outside ambient pressure; exit pressure lower than ambient pressure is referred to as overexpansion. There is not an exact ratio at which flow separation occurs, but common estimates are in the range of P_exit/P_ambient = 0.2-0.4. The pressure difference at the nozzle exit leads to the lower pressure exhaust being "pinched" towards the center axis by the higher pressure ambient gas. If this force becomes too high, likely in the range of the ratios mentioned, the nozzle flow will detach from the walls of the nozzle, which is called flow separation.
To optimize the performance of a rocket nozzle, the exit pressure should be as close to the ambient pressure as possible; since vacuum engines are optimized for in-space use, the exit pressure is extremely low. The exit pressure will be controlled by the expansion ratio or area ratio of the nozzle (A_exit/A_throat); for vacuum engines, we see much larger nozzles in order to maximize the expansion ratio and minimize exit pressure.
So, to briefly answer your question:
- Rocket velocity (or Mach #) is not the same as nozzle exit velocity
- Flow separation ("air sucked in") is dependent on the ratio of nozzle exit pressure to ambient pressure, not on rocket or nozzle exit velocity.
- Even at high altitudes, the vacuum nozzle would generally still be overexpanded and be at risk for flow separation.