Answer: The three denominations are $65$, $72$ and $97$.
How did I detect this answer? I searched the list of primitive Pythagorean triples at [link to triple list], while using the Frobenius applet available at [applet link]. Based on my search I know that the answer to the puzzle is unique; still, I would like to see a clean mathematical argument for this (that is not based on enumeration).
Even proving that all values from $1000$ onwards are representable is very tedious. I checked $65$ underlying individual cases with a computer program.
The proof that the value $999$ is not representable is doable. Suppose that there exist non-negative integers $x,y,z$ with $65x+72y+97z=999$. By considering the equation modulo 9, we get that $x\equiv z \pmod9$. By considering the equation modulo 2, we get that $x+z$ must be odd. Since $0\le x\le15$ and $0\le z\le10$, this only leaves a handful of subcases with $x=z+9$ or $z=x+9$; none of these subcases yields an integral value for $y$.
I have also found a [scientific paper] that provides an explicit formula for the Frobenius number of primitive Pythagorean triples:
$$ F(m^2-n^2, 2mn, m^2+n^2)=(m−1)(m^2−n^2)+(m−1)(2mn)−(m^2+n^2).$$ By setting $m=9$ and $n=4$, we recover the solution $65$, $72$ and $97$ for the Pythagorean coin puzzle as stated above.