There isn't anything nondeterministic about garbage collection systems; it is just that it is hard to predict how much time they will take for a call.
However, the same can be said about classical C style memory management. An alloc can be almost immediate or take lots of time because it has to request a fresh memory block from the OS. Similarly, a free can or cannot take time to coalesce blocks.
Yes, the differences are much smaller there, certainly historically, but garbage collectors have improved, and I am not sure that C-style allocators can stay predictable in long-running programs. Let's say you have a terabyte of RAM, and want to run a multi-threaded server in it 'forever'. Chances are that your garbage-collected system will be more stable and use less memory because it can compact memory. A C style allocator would need quite a few heuristics (or maybe, even contain some machine learning code that builds a model of memory allocation patterns) to prevent memory fragmentation. Such features would make their timing less predictable.
Because of that, I think we may at some time see an OS with built-in garbage-collection become mainstream.