The administration and maintenance of Microsoft Exchange Server to ensure secure, reliable, and efficient email and collaboration services across an organization.
From that, I'd say you are being greylisted by 365. Did the external sending IP change when you migrated to a new server? Is the cert used on the 2016 cert correctly applied to the send connector and matching the FQDN?