>Looking of the details in the document below, it suggests it's possible, but only if the MX sees the DNS request to match it up with the client connection.
The DNS request can be either inter-vlan or go out to the Internet or out AutoVPN to another site. The DNS request populates the DNS cache. The FQDN firewall rule then uses this DNS cache.
Consequently, it does not matter who made that DNS request or which DNS server it was sent to.
You do need to be careful with short-lived DNS results or queries that always return a different result with a short TTL. For example, from memory, Facebook uses a TTL with 60s. So you can get a case where client "x" does a lookup. Client "y" does a lookup a short time later but gets a different result. The firewall rule ends up using only one of these results, so one client works and the other does not.
Something like that. Explanation not exactly right. But jist is.
On the whole, it works great with most cloud providers using rotating sets of IPs, but not all of them (only a small percentage that don't work well).