The core of the difficulty is that although timestamptz_out is getting called, that's nowhere visible in the parse tree. I suppose we could decide that it's illegal to allow array_to_string() or format() to exist, but I don't think anybody will like that answer.
Yeah. The user expectation (and arguably architectural ideal) that the output representation of data types is immutable being violated is the bigger issue here but one that we are basically stuck with. As you note below, however, since real complaints mostly manifest in polymorphic situations, coming up with a solution at that scope, one that makes function volatility a planning time property instead of a create function time one, makes the most sense. Since the function is being defined for planning time type resolution, extending that to volatility is internally consistent.