This might be due to how the DNS server itself provides the information. There are services which have dozen on IPs assigned to it.
If one does a name resolution (nslookup on Windows, host on Linux) of mail.office365.com, the result will be different every 10 seconds or so. This permits the provider to distribute to load among the different servers.
If the destination will be called using web protocols, using an URL instead of fqdn might solve the issue. If the application is something different, then you have to fetch all possible IPs and add them to the policy (or an object-group).
... View more