A negation of a $in with a regex cannot be indexed. This is enforced by the query planner's index selection phase here:
However, a negated $in with a regex, and one without a regex, are considered the same shape. This can be seen by verifying that they have the same queryHash, which was added to explain output in SERVER-36527:
MongoDB Enterprise > var hash1 = db.c.find({a: {$not: {$in: [32, 33]}}}).explain().queryPlanner.queryHash MongoDB Enterprise > var hash2 = db.c.find({a: {$not: {$in: [34, /bar/]}}}).explain().queryPlanner.queryHash MongoDB Enterprise > assert.eq(hash1, hash2)
As a result, the latter query can incorrectly use a plan cache entry created by the former query. The resulting plan has incorrect bounds which can erroneously exclude matching documents. A likely fix would be to add a discriminator to the plan cache key so that $not-$in predicates with regexes are encoded differently from $not-$in predicates without regexes.