That gets a bit tricky in terms of what you mean by valid programs. I presume what you mean is that you can't write a compiler that accepts every function which always returns the borrowed reference and reject every piece of code which fails to do so.

Though it's technically a bit different than the halting problem as this issue remains even if you assume that the function terminates -- you only want to show that the reference is returned assuming the code terminates if it isn't returned because it enters an infinite loop that's not a leak.