What databases are those? If you convert to a semijoin, both strategies should be doable.

Note that these caveats do _not_ apply to IN, only NOT IN.