Determinism is an absolute, objective concept — either a process always produces the same result, or it doesn't.
Well, no, it's not so simple. When people say that something is deterministic, they're often leaving out a precise specification of just what it means for the process to be executed in the same conditions. A deterministic process always produces the same result for a defined set of initial conditions. It matters what you consider part of the process and what you consider part of the initial conditions.
Concurrency is an extreme case of non-determinism. In pretty much any model of concurrency, scheduling introduces a source of non-determinism, and the most we can expect is that one thread or node behaves deterministically, if the behavior of the rest of the system is constant from its point of view. Any timing difference causes the thread to observe the rest of the system in a different way, which allows it to behave differently.
Input/output can cause a program to behave differently. Again, very much like a thread in a concurrent system, a program that performs I/O is only expected to behave deterministically if its interactions with the rest of the world are fixed. A sequential program that doesn't perform any I/O (including things like calls to random number generator) is expected to be deterministic. Its behavior is thus fully predictable and reproducible. Let's call such a program a pure program.
What this means for memory management is that a pure program is deterministic, no matter what memory allocation strategy is used.
Now as hinted above this statement needs to be qualified. What assumptions are hidden here?
An important assumption is of course that the memory allocation strategy is fixed, and non-randomized. A different memory allocation strategy could obviously lead to different behavior, including the memory being full or not full at different times in the program's execution.
Another assumption is that we're talking about a complete program, starting from a known initial state. As far as memory management is concerned, we're running the program starting with a fixed heap configuration.
But what if we were talking about a program fragment? We tend to like our notions about programs to be compositional, because we're forever building bigger programs from components. Depending on where and how a given program fragment is executed, it may be started from different heap configurations.
Garbage collection affects the heap globally. If a collection happens during the execution of the program fragment, it may also affect storage used by the rest of the program. Thus garbage collection exhibits a strong dependency on the program as a whole. An object that stops being used may or may not be collected because a collection may or may not be triggered at a particular point, or because the minor heap may fill up at a different time for a generational collector, etc.
Reference counting is more deterministic than garbage collection because there are fewer dependencies to the rest of the program. An object used solely by the program fragment is freed when its reference count reaches 0, and this does not depend on the what the rest of the program had been doing.
Reference counting, like most memory management strategies, is not fully deterministic from this point of view. The state of the heap when the fragment starts matters because of fragmentation. Even for a given amount of free memory when the fragment starts, a difference in size and layout of the free areas may lead to the program running out of memory, or not. The amount of time spent managing the data structures of the memory allocator may also vary depending on the shape of the free areas in the heap.
This is the case for any memory allocation strategy, including fully manual management, except for strategies guaranteed not to run out of memory (such as fully static allocation).
Just about any memory allocation strategy is non-deterministic in the sense that the behavior of a program fragment is affected by the surrounding program — both in terms of whether a given allocation will succeed (and at which address), and in terms of how much time is spent on memory management at any given point. The difference between reference counting and garbage collection is not one of nature but one of degree. Reference counting is more deterministic than garbage collection (under typical approaches). And that's without getting into concurrency, where pretty much anything is non-deterministic.
Arguing whether a strategy is “deterministic” without enough context to precisely specify what is meant is a matter of semantics. In the colloquial sense of “arguing about words and forgetting about their meaning”, not in the technical sense of “the study of the meaning of programs”.