domain name – Update MX record causing rebound

We recently migrated our company to a new email provider (Gmail) and updated our MX / SPF / DKIM / DMARC records.

By checking the DNS propagation via https://dnschecker.org/, all changes are reflected.

However, when you try to send an email to a specific person, we receive the following non-delivery report:

This is an SMTP server on asp.reflexion.net

Your message could not be delivered to the following address: <**redacted**>

of <**redacted**> at <**redacted**>
** redacted **. mail.protection.outlook.com:***.***.***.*** failed after sending the message. STARTTLS proto = TLSv1.2; Number = ECDHE-RSA-AES256-SHA384.
Remote host says: 550 5.4.1 All recipient addresses are rejected: access denied [**redacted**.protection.outlook.com]

A tip on how to solve? Is it simply a cache problem on the part of Outlook that will be resolved over time, or are there any configuration issues that we need to resolve on our side?