Or maybe, just maybe, LLMs do not run deterministicly and that is ok?

In the real world almost nothing runs like that - only software and even that has a lot of failures.

So perhaps rather than trying to make agents run deterministicly the goal is to assume some failure rate and find compensation control around it.