"This e-mail message cannot be delivered to Bob because the email address is no longer valid."

Hi @Mark Zanders ,

Thank you for posting to Microsoft Community. We are happy to help you.

To help you better, we want to confirm the issue is that you got the email address is no longer valid message when you send message in desktop Outlook while it works fine in Outlook Online （OWA, Outlook Web App）.

If this user can access his mailbox in OWA and can send/receive messages without any errors, the issue could be related to cache of Outlook client. You could try to disable and re-enable cache mode of Outlook by clicking File > Account Settings > Account Settings and select your account, then unselect/select check box next to “Use Cached Exchange Mode to download email to an Outlook data file” as below show. Please remember to restart Outlook client to make it take effect.

I also suggest you create a new Outlook profile for the problematic user and test this issue:

Creating a new Outlook profile will not affect existing profile. For more information about how to create a new profile, please refer to this article:

Create an Outlook profile

https://support.office.com/en-us/article/create-an-outlook-profile-f544c1ba-3352-4b3b-be0b-8d42a540459d?ui=en-US&rs=en-US&ad=US

If there is anything else you need help, please feel free to contact me.