Reported the same problem yesterday. But I say it again simple additional test case will do, e.g.:
Assert.AreEqual(20000000001, Kata.NextBiggerNumber(12000000000));
good solutions pass it in milliseconds and brute force will always time out.

next_permutation will never be not performant enough. But you can ban using next_permutation, prev_permutation and the # character (and compensate for the lack of # by including potentially useful headers like string and vector and probably even algorithm in preloaded). I can't immediately think of a way to bypass it; if there is some then it would be at least not too obvious.
UPD And ban %: too.
UPD Actually, it's still possible to use preprocessor even after this. So unstead of # and %: it's better to ban include and define.
UPD It should work with either banning # and %: or include and efine but in either case possible line continuations inside tokens should be considered.

Can you make it so that the number and the scope of the random tests would make using std::next_permutation not performant enough?

In case, go for it!