Outlook for MAC / Exchange 2013 – Can’t reply to some mail addresses hosted on the same Server

Hello everyone, 

I have an odd behaviour with an outlook for mac client from a colleague connected to an Exchange 2013 (Hosted) : 

When this Client receives a mail from e-mail users on the same server - same organisation or different doesn't seem to matter - the user name is sometimes (not always) flagged with a red ? next to it. 

When the client replies to this mail it won't send and gives an error messages that this e-mail address cannot be found. 
(No other Clients like Outlook for Windows / iPhone etc show this behaviour) 

If the user then clicks on that username to open the contact it will open one of his private contacts (not in any way related with name or mail) instead of the correct user and contact folder on the server. 

As no other users / clients have reported this issue I guess it is a client problem, but i might be wrong on this ;)

Anyone else saw a similar behaviour with outlook for mac connected to an exchange server ? 

thanks in advance - any hints welcome 

Florian S