"Deterministic" only insofar as it's repeatable, but their behaviour is not predictable. If the behaviour is not predictable, how can it be validated as being correct?
I'm not sure what you mean with "is not predictable" when you also admit that it's repeatable.
But AI isn't different than existing software systems either. Both will take an input from reality and take actions upon it.
Repeatable means you get the same output a second time, given the same input. Predictable means you can say in advance what it will do, and can then check the output against your prediction.
If you can't predict the outcome, you can't validate the process, and can't guarantee its performance.