While water will break down at high temperatures I would find it surprising that 1st and 3rd most common elements in the whole universe, that readily combine to form water would not result in substantial amounts of water.
It's probably like saying we shouldn't find H2 because "nothing says they are found bound together"
Most atoms- and certainly most hydrogen- are in stars, no? Not exactly places where water "breaking down at high temperatures" (really, never forming) can be ignored.
