At the point where the kernel knows that it should be returning a null pointer, you're probably already operating in a severely degraded state
That's only currently the case. It doesn't need to be. As per your example, you could just as easily provide an upper bound to the page table scan, and return NULL when enough pages can't be found in 100us.
It's not possible for a program to react gracefully to a system OOM.
A program should never receive a system OOM, the fact that Linux' memory accounting is so bad the system itself can run OOM is the problem. It is perfectly possible for a system kernel to execute in bounded memory, and never let programs claim parts of that. Linux just isn't designed that way.