Can I use the set of "used arguments values" as a memoization key for a deterministic function?
As long as $f$ is deterministic and depends only on its arguments (not on other global variables), yes, you can safely use that as a memoization key.  The bad case cannot happen.

You can see this by thinking about what happens as it reads the $t$th argument and using induction on $t$.  Let $i_1,i_2,i_3,\dots,i_t$ be the sequence of argument indices read (i.e., $f$ first reads $i_1$ when running on input $x$, then reads $i_2$, etc.).  For each $t$, if $f(x)$ and $f(y)$ have behaved the same up until just before they read the $t$th of these, then the next index examined by $f(x)$ and $f(y)$ will be the same, say $i_t$; if additionally $x_{i_t} = y_{i_t}$, then it follows $f(x)$ and $f(y)$ will behave the same up until just before they read the $t+1$st of their arguments.  Since $i_t \in U_X$, $x_{i_t} = y_{i_t}$ is guaranteed by your assumptions. Now use induction.

This assumes everything is deterministic.  For instance, $f$ had better not be allowed to read a random-number generator, the current time of day, or other global variables.  Beware that on some platforms there can be surprising sources of non-determinism, e.g., due to aspects of behavior that are unspecified and might depend on external factors.  For instance, I have a recollection that floating-point math in Java can introduce non-determinism in some cases, and so if you want to write code that is verifiably deterministic, you probably want to avoid all floating-point math.