TL;DR Update UPN and wait at least 24 hours.
During setup of M365 Bookings shared calendar, a company account is created with user principal name (UPN) in the format of [email protected]. This UPN is used as the sender address when sending out booking notifications. The issue is that *.onmicrosoft.com email domain is often abused for spams and many email providers (notably iCloud) are starting to reject any incoming email with that domain. Microsoft meanwhile has started to throttle usage of that domain for sending email.
There are two ways to update the sender address:
Method (1) is the Microsoft’s recommended method, but I prefer Method (2) due to visibility on Entra ID; anyone with read-only account within the tenant can view the updated UPN in Entra ID whereas only M365 admin can view mailbox policy. If a subdomain (e.g. [email protected]) is preferred over the company’s email domain (example.com), the subdomain will need to be added to M365 with MX (booking-example-com.mail.protection.outlook.com), SPF ("v=spf1 include:spf.protection.outlook.com -all") and DKIM DNS records, regardless of method (1) or (2).
If the booking calendar is embedded in the company website, the iframe link https://outlook.office365.com/owa/calendar/[email protected]/bookings/ needs to be updated to https://outlook.office365.com/owa/calendar/<new-upn>/bookings/.
Once UPN is updated, it may take at least a day for the change to apply. In my experience, the new UPN is applied to new appointment’s notification within hours, but it only applied to cancellation notification after 24 hours (or longer).