From the perspective of a far-away observer, matter falling into a black hole never crosses the boundary. Why doesn't a basic symmetry argument prove that Hawking radiation is therefore also frozen on the boundary, and therefore not observable? Wouldn't the hawking radiation have to have started its journey before the formation of the black hole? Furthermore, wouldn't the radiation be infinitely red-shifted?
Classically, this is true. Something exiting from a classical static black hole would have had to have started before the universe was created. The frozen-on-the-horizon view of a black hole is the view you get under classical general relativity. When you add quantum mechanics, this view is no longer quite valid, and you get Hawking radiation, which from a far-away observer's viewpoint, interacts with the infalling matter.
Evaporating black holes behave qualitatively differently from static ones if you allow an infinite amount of time to pass. In particular, there is no event horizon for an evaporating BH, only an apparent horizon. Furthermore, if you stack the apparent horizons of a shrinking black hole plus time, the resultant surface is two-way transversible.