"Linux, for instance, does not support arbitrary call depth and barely uses recursion." Perhaps there's context missing from that statement? Linux certainly can have arbitrarily deep call depth, depending on the stack size. Are you referring to the kernel? That would be odd, since the paper talks about application code needing to be fully recompiled with retpoline to be safe.

(Of course, that means that all libraries you link with or dynamically load have to be compiled with retpoline too.)