We just started using Microsoft 365 and have quite a few users that are using outlook.com only (no local outlook client).
Outlook.com looks to populate the autocomplete automatically by searching the directory however it is pulling back UPN addresses for the users instead of their actual email address. When you then select this it is not able to send the email.
Example would be the persons email would be firstname.lastname@example.org but then when they search, they would see user but below it is showing [upn: <email@example.com>] instead of their regular email. It is not consistent either because some people show correct. You will see in the attached image that some show UPN and the last in the list shows the right email.
In the example i attached the person who is showing correct has a business premium license where the others all have business basic. Not sure if that matters but it is the only difference I can see