The DNS setup was as follows:
Apex domain has an A-record, since it cannot have a CNAME record, pointing to one of Umbraco Clouds IP addresses.
Wildcard CNAME record (*.domain.com) pointing to dns.umbraco.io.
Changing the CNAME value from dns.umbraco.io to the root domain solved it.
This, along with the fact that there hasn't been any issues with the previous settings until approx. 14 days ago, confirms, at least for me, that there is an issue with dns.umbraco.io, something must have changed.
I'm suspecting Umbraco has changed something on dns.umbraco.io because of upcoming changes to Cloudflare IP addresses.