"Network settings
Some organizations might be required to audit all network traffic by policy. To comply with such a requirement, these networks can block access to Private Relay. Users will be alerted that they need to either disable Private Relay for the network or choose another network. The fastest and most reliable way to do this is to return a negative answer from the network’s DNS resolver, preventing DNS resolution for the mask.icloud.com and mask-h2.icloud.com hostnames necessary for Private Relay traffic."
https://www.apple.com/privacy/docs/iCloud_Private_Relay_Over...
Apple can probably improve the situation by making Private Relay more like a VPN (instead of a fancy web proxy + DNS masker), including reusing the same IPs and domains that iCloud traffic is already going through.
Edit: Apple's docs show two well-known subdomains for Private Relay[1]. Blocking both of those is probably what Verizon's doing.
[1]: https://developer.apple.com/support/prepare-your-network-for...
Edit: woodruffs above provided docs
One option that works for me to get custom DNS on iOS cellular connections (I like PiHole ad blocking on my phone) was to setup my own VPN connection to a VPS instance running PiHole for DNS and WireGuard for the VPN. Lets me get custom DNS, pihole adblocking over cellular so long as VPN isn't blocked by your cellular provider etc. Was two trivial Docker containers to get running, costs very little in AWS.
Same trick also lets me access region blocked TV services from my iOS devices over US cellular simply by turning a VPN on - I just stand up the containers on a VPS host based in source country and connect to that.
like Tor exit nodes, or obfs4 bridges
turn it into a war of attrition!