If the language subset can't loop, can't recurse, can only call functions that are guaranteed to finish in finite time, and only allows finite-length programs, then its programs will always halt in finite time.

Fixing eval is almost exactly what the OP does. It's not that hard. Everyone who has written a toy lisp can do it.

The key to solving the halting problem is realizing that you don't need to solve the halting problem.

Problem : Code C has to run in finite time T, Solution : put a call to a watch dog routine at every loop start, at every subroutine start, and every n linear instructions in C. If the watch dog decides T has passed, it never returns control to the program (calls exit(-1), throws a special uncatchable exception,...). This can be automated by the compiler.

This is why AWS can give you a limited time for a Lambda or why every single multi-tasking OS can terminate an unresponsive process. They are not solving the halting problem.

If the language C is written in is bytecode-interpreted, you don't need to modify the guest program itself to achieve the described effect, you can make the interpreter itself keep track of T and refuse to evaluate further when it runs out. If the execution environment is preemptively concurrent, you don't need to modify the host program as well, simply make the watch dog preempts the guest at T.