A record required for MX record?

Previously our domain, let's call it ourdomain.com, pointed to an IP address (our web host). In addition, we use Office 365 to handle our domain email accounts. DNS records:

ourdomain.com    A        XXX.XXX.XXX.XXX
ourdomain.com    MX 10    our-domain.protection.mail.outlook.com   

Now we have moved to Azure's cloud environment. It is recommended to not use A records and rather CNAME records, as IP addresses are not guaranteed to be retained.

So we removed the A record and added the CNAME:

ourdomain.com    CNAME    ourcloudsite.cloudapp.net
ourdomain.com    MX 10    our-domain.protection.mail.outlook.com       

Now our email is not being received. The result of an nslookup for MX records on ourdomain.com is also incorrect.

I've read that we need to have an A record for MX records to resolve. What A record are we supposed to use then?

We could use the IP of ourcloudsite.cloudapp.net, but then we risk having downtime.

You can't use a CNAME record at the zone apex. This is because a CNAME record defines one name to be an alias of another regardless the requested record type.

This, in turn, also means that a CNAME record cannot coexist with other records as that would be a conflict/inconsistency.

The zone apex always has at least SOA and NS records, which means there can never be a CNAME there.

As the CNAME suggested by the service provider is not an option, one possible solution to avoid the risk of being caught out by an address change (that would work specifically for a web site) would be to instead add an A record pointing to an address of a different web server that does have a static address. This server would be set up to do an http redirect (301) from eg http://example.com/ to http://www.example.com/, where www.example.com is then set up with the CNAME record suggested by the service provider.

(It's quite likely that you would want to redirect one of the names to the other anyway, one usually does not want all resources to be duplicated with multiple URIs.)