"Undeliverable" email address, but only for first time emailing someone?

Question

Short version:

I am unable to email new contacts associated with a specific organization when manually entering their email address. I receive an Undeliverable email from Microsoft whenever emailing someone for the first time (within organization). Double clicking someone's contact link from the staff directory associated with the org allows me to email them successfully, but manually typing in their email address returns Undeliverable.

Note: I am typing out email address exactly as it appears in directory, and I have verified there are no spelling errors or special characters.

Long version:

I am attempting to email a user within a specific organization -- their email address is usually in the format [e-mail]. Sometimes it deviates to something like [e-mail]

When using the staff directory associated with myorganization.org, I can use the link for someone's email address to open a new email window and successfully email them.

If I copy and paste the email address (exactly as it appears) from the directory, any email I try to send returns Undeliverable. Hovering over the email address I typed also displays no information.

If I successfully email someone for the first time (using contact link), then I manually enter their email address into a new email, then my second email is successfully sent.

So, my email is failing to send first email to a new contact when manually entering their email address. If I email them once, then manually enter email, there are no issues.

Note: I only experience this issue using Microsoft app installed on my computer. When emailing someone from web browser version of Exchange, I do not receive any errors (even if I am manually typing the email address vs. fetching from staff directory. Consequently, I believe the issue has something to do with my computer and/or app, rather than the Exchange platform itself.

Is this a Microsoft bug? Am I doing something wrong here? I just want to manually type in email addresses for new contacts who I wish to email, without having to go through the staff directory to find their contact link and email them.