Is every single large solid body orbiting entirely outside of the frost line covered in ice? Not sure where I heard that but I want to make sure if it's true. Forget about the asteroid belt for a minute: Are all the moons of the outer planets and kuiper belt objects covered in water ice?
No, they aren't all covered in water ice.
As an example, Io, a moon of Jupiter is covered in volcanically deposited sulfur and sulfur dioxide frost.

Solar system mechanisms are pretty complex and varied, so we wouldn't expect similar quantities of water as exist on Earth.  Also, the &quot;frost line&quot; for water in the Solar System isn't the same as the &quot;frost line&quot; for many other compounds like Ethane and Methane.  Saturn's moon Titan has lakes of the stuff:

Instead of water snow, Titan has benzene snow that dissolves as it falls in the lakes!  Delightful...