The key to this is the physical principle that the quantity you're asking about (delay between noise and noise cancelling) carries dimensional information (i.e. it's a time) and therefore it has to depend on the specific situation.
The simplest case is trying to cancel out a pure note, with a sinusoidal waveform, then the delay can be as long as you want: you just wait a whole number of periods and it doesn't change anything. (The delay precision, though, has to be quite high! The absolute delay can be as large as you want, but its precision must be much smaller than the pure note's period (1/its frequency) for the noise cancelling to work.)
A pure note, however, is not really a physical thing. All sounds have a finite duration, and therefore a more physical model is a finite waveform such as
(image source)
Here it's clear that you can't wait forever, or the "noise cancelling" will just be an echo. The relevant timescale your delay must act on is that in which the pulse is changing. This is given by the input's bandwidth: you can represent your noise as a (Fourier) superposition of pure notes drawn over some interval of frequencies $[0,\nu_\text{max}]$; the shortest timescales over which the waveform can change are of the order of $1/\nu_\text{max}$. This is the maximum delay for the noise-cancelling system to be effective.
In practice, it works the other way. Such systems have a fixed delay, which determines which noise bandwidths they are effective against. Designers try to make their headphones effective against most usual sources of noise, but this can't always be managed. Some systems (including the headphones I'm currently wearing) include a choice of bandwidths - mine says "low" and "wide", best for trains and airplanes or viceversa - to adapt to different noise sources.
The bottom line, then, is an emphatic yes to your second question. The delay should be shorter than 1/(highest noise frequency) for whichever source you're dealing with.