We currently have a mixed environment for Exchange.
We have Exchange 2007 hosting some on-premise mailboxes, Exchange 2010 connecting us to Office 365 and I've just installed Exchange 2013 which I am going to move all on-premise users to and decommission the Exchange 2007 and 2010.
The problem is new users are not appearing in the address book. So if I try to resolve a new user using the address book I we the errors attached. If I try to send the email I get the bounce back attached. Its coming from the Exchange 2013 server.