Expanding the title I am trying to prove that $\forall x,y,z\ (h(x,h(y,z))=y)\rightarrow \forall x,y\ (x=y)$ is a logically valid formula of the first order language $L=\{h\}$, made by a single function of ariety 2.
It is clear to me that we should reason on the fact that, $h$ is a function which " extracts information" both from the first and the second of its arguments. Hence if there are $x\neq y$ we may try to build an interpretation of $h$ so that $h(x,h(y,z))=y$ does not hold.
I have tried to play around substituting different terms (which we can obtain, I observe, only by application of $h$ to variabnles) as arguments, e..g. $h(h(x,y),h(x,y))=x$ but haven't quite reached an intuitition.
I know that there is not an algorithm to decide whether a formula is logically valid (the problem is semidecidable), but can we resort to some heuristic at least?
Your heuristic is indeed correct. The proof is as artificial as the problem, but ultimately not difficult.
First, we can prove that for all $z$, the partial function $h(-, z)$ has to be injective. For if there are $y, y'$ with $h(y, z) = h(y', z)$, then $y = h(z, h(y, z)) = h(z, h(y', z)) = y'$.
But now suppose there are $x, x'$ which are distinct. Then by injectivity in the first argument of $h$, we would need that $h(x, h(x, x)) \neq h(x', h(x, x))$. But by definition, both sides of this are equal to $x$. Thus the domain contains only one element.
Edit: We can significantly simplify this argument as just a sequence of equalities: simply take $x, y$ in the domain, and then $$ x = h(x, h(x, h(x, x))) = h(x, x) = h(x, h(y, h(x, x))) = y. $$