Thanks!

Some additional context:

- I checked online and they do have this email address listed on their pages

- This affected 2 separate domains served by Microsoft

- I sent them an inquiry email now from my @gmail.com and no bounce was returned so far

EDIT: Also gmail got the error response, so I guess it's really up to the outlook server these unrelated entities use...