Terrible. The official method for blocking iCloud Relay is via DNS: https://developer.apple.com/support/prepare-your-network-for... I wonder if this is what they're doing.

If so, it's a hassle, but you can specify custom DNS servers (even DoH and DoT) for mobile connections using a .mobileconfig file. https://dns.notjakob.com/ can generate them for you.

Probably a good idea to do this anyway to keep your carrier from spying on your DNS requests.