Given that they all use pseudo-random (and not actually random) numbers, they are "deterministic" in the sense that given a fixed seed, they will produce a fixed result...

But perhaps that's not what was meant by deterministic. Something like an understandable process producing an answer rather than a pile of linear algebra?

You can just change your definition of "AI". Back in the 60s the pinnacle of AI was things like automatic symbolic integration and these would certainly be completely deterministic. Nowadays people associate "AI" with stuff like LLMs and diffusion etc. that have randomness included in to make them seem "organic", but it doesn't have to be that way.

I actually think a large part of people's amazement with the current breed of AI is the random aspect. It's long been known that random numbers are cool (see Knuth volume 2, in particular where he says randomness make computer-generated graphics and music more "appealing"). Unfortunately being amazed by graphics and music (and now text) output is one thing, making logical decisions with real consequences is quite another.