I don't see how the privacy policy wording can be interpreted that way.
The wording you've clipped does not suggest that the "unique, anonymous identifier" will be sent to every website. (It does suggest there's a customer choice in some way, but that's unclear and so far no one has reported a reliable way to have Verizon suppress the X-UIDH header.)
The note that "many opt-outs are cookie-based" may not be relevant to this tampering. In particular, there's no clear way that cookies to Verizon websites could be consulted when doing the tampering on each HTTP request to other websites: they're not part of the connection. (I suspect this section is boilerplate related to some other opt-out.)
Maybe the header isn't being sent for you due to this change possibly being a gradual rollout.