From what Graham said, it seems as if the server does have a static IP, but the DNS routing is some form of dynamic arrangement.
I have this (successful) situation with Symantec Email Security.cloud filtering. They process incoming and outgoing emails and relay them to/from Smartermail and other email servers that I maintain. "cluster5.us.messagelabs.com", for example, is in the MX record. They give this, or variations on this, to different accounts. The secondary MX entry would be, for example, "cluster5a.us.messagelabs.com".
Outgoing emails are sent from this cloud service using one of many outbound IP addresses - yes they do change all the time - and this routing works just fine.
I've been using this service for several years (back then it was called Messagelabs). Interested to know the final resolution of Graham's issue.