Is Optical VLBI theoretically feasible? If not why not? There are plenty of optical interferometers in use with baselines of up to maybe 1km. As far as I can find out, they all work by directly collecting the light at all the telescopes, using mirrors to bring them together and then actually interfering them and observing the fringes with photodetectors. 

Meanwhile, radio astronomers do interferometry over distances of thousands of km, but they do it quite differently. Essentially, they record the baseband electromagnetic waveform at each telescope, with an accurate timestamp, transport them all to a central location and combine them computationally. 

So my question is whether in principle you could use the radio astronomers methods with an optical (or near IR) signal. Obviously the engineering and computational challenges would be formidable -- you would need to record data at speeds close to 1 Pb/s, timestamp it with femtosecond accuracy and do a ludicrously huge computation to recover an image, but that's not my question here.

On the one hand, it seems like the answer should be "yes" -- electromagnetic waves are electromagnetic waves. On the other hand, why should the phase of a photon observed in one telescope have anything to do with the phase of one observed in another? If you are digitising the data at each telescope, you are ruling out interference  fringes on a quantum level, just as happens if you find a way to measure which slit a photon went through in the double-slit interferometer. This suggests that the answer should be "no".

If the answer is "no" then what wavelength does the cutoff happen at? We have radio-style VLBI at 1mm now and optical-style interferometry at 1 $\small\mathsf{\mu m}$, what is possible in between?
This question amounts to: is optical interferometry possible when detecting photons? The answer to this is yes. Many experiments have been done using interferometers where one photon at a time is passed through the apparatus and still reveals an interference pattern when detected on the other side.
The problems with optical interferometry are manifold: optical interferometry at the moment relies on bringing the signals together in hardware; there is an immediate problem with applying the radio interferometry technique of &quot;taping&quot; the data and doing the correlation offline, which is simply that the bit rate of the higher frequency optical light is far too high to do this at the moment. I have to admit ignorance as to whether this will be possible in the forseeable future. There is an obvious issue in recording the time of arrival of photons more accurately than the uncertainty principle allows for even the fastest optical transitions of $\sim 10^{-8}$ s, which is well below the resolution needed to sample frequencies of $\sim 10^{15}$ Hz. (Edit: the fastest detectors don't use transitions in atoms and can achieve timing of $10^{-10}$ s; still too slow by orders of magnitude.)
However, even if you could &quot;tape&quot; the data, there are many other problems to be overcome. These difficulties mostly relate to the coherence length and coherence time of phase changes introduced in the atmosphere above each telescope and the inability to use phase-reference sources as a result; and the inability to use phase-closure techniques unless the sources are very bright. These difficulties are explained in more detail in https://astronomy.stackexchange.com/a/35215/2531
To summarise, telescopes in different places observe the same object through different atmosphere. This introduces phase errors. These can be calibrated out in radio observations by using a nearby reference source. This is because the phase errors persist over a reasonably long time and are similar over a reasonably large (&quot;isoplanatic&quot;) patch of the sky. For optical observations, the isoplanatic patch may only be a few arcseconds across, so there is rarely a bright reference source, and the atmosphere changes in any case on timescales of tens of ms.
Optical interferometers get round this by using phase closure techniques. The phase error can be eliminated by comparing the phase differences from at least three stations. But again, you have to do this on very short timescales and this means optical interferometry is limited to bright objects in order to get enough signal.
Where is the cut-off? Well certainly beyond the near-infrared, because those interferometers also use similar techniques (delay lines, phase closure) in their techniques.