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$.