• For all your Exchange users and groups, make sure Exchange mailbox alias field does not contain spaces or characters other than a to z (uppercase or lowercase), digits from 0 to 9, !, #, $, %, &, ', *, +, -, /, =, ?, ^, _, `, {, , } or ~. One or more periods may be embedded in an alias, but each one of them should be preceded and followed by at least one of the other characters. The @ symbol is not allowed in an alias.
• For all your Exchange users, make sure the UserPrincipalName (aka Logon name) is "user@domain.com" and not just "user". I have seent that this problem is usually found on users that are created in Active Directory by Cisco Unity.
• Make sure your display names do not contain leading or trailing white spaces, i.e. the first and last characters in a display name cannot be a white space.

Usually these kind of problems are found in large environments where user provisioning is automated by a third party application or script. If any of the above conditions apply, Exchange Management Console (or get-recipient shell command) will warn you of inconsistent Active Directory objects.