We have moved our email hosting from our old hosting provider to Office 365, however, we still receiving some emails on our old email provider.
It doesn't look like a DNS replication issue as it has been nearly a month now. It seems to me that the original hosting company's mail servers are simply not checking our MX records as they still think the account is hosted by them.
Is it normal to see emails sent from an old mailbox not go to the mailbox on the new system, and what would be the best way to ensure our emails go to our new mailboxes in future?
Some email systems, Exchange included, will perform an internal discovery for the recipient first and deliver mail locally, before even looking at the MX record. Depending on the system in use, you might have several options available to deal with this: remove the already migrated accounts, configure forwarding, change the delivery settings (in Exchange you change the domain type), etc.