Process mail flow rules first
If an employee leaves the company then we archive the mailbox to PST and unlicense the account but the employer wants to redirect the emails so we would like to create a mail flow rule to do this for easier management but emails are rejected with a reason of "Unknown TO address" so Office 365 must be checking the list of email addresses in Exchange but not the mail flow rules.
Jon Webster commented
You can also convert the mailbox to a shared mailbox before removing the license to leave the object mail enabled.
Ben Hooper commented
I've discovered today that you can work around this by creating a mail contact for the missing email address. I also discovered that redirecting an email to multiple recipients does actually work even though the message trace states that it was only redirected to one.