We're using Standard offering of Verizon CDN in Azure. From the documentation it's clear that Verizon gives priority to other compression schemes over Brotli if the client supports multiple ones (https://learn.microsoft.com/en-us/azure/cdn/cdn-improve-performance#azure-cdn-from-verizon-profiles):
If the request supports more than one compression type, those compression types take precedence over brotli compression.
Problem is that our origin gives priority to Brotli. So for a request with Accept-Encoding: gzip, deflate, br header directly made to the origin, the response comes back with Content-Encoding: br header. However, the same request going through CDN comes back with Content-Encoding: gzip.
Azure's documentation isn't clear on what occurs here. Does the POP node decompress the resource and re-compress with gzip and cache? Does it decompress and cache, then compress on the fly based on the request's header? I posed the question to Azure support and sadly didn't get a definitive answer.
I have finally got a conclusive answer from Verizon. The Via header from CDN's POP node to origin was effectively disabling the compression (this page would explain it better: https://community.akamai.com/customers/s/article/Beware-the-Via-header-and-its-bandwidth-impact-on-your-origin?language=en_US). Handling that in our web server (either strip the header or configure the web server to compress regardless) solved the issue. In other words, if the client support Brotli and origin prefers Brotli, Verizon's CDN caches and uses the content compressed with Brotli.
In other words, Microsoft's documentation is misleading and incomplete.