The name cannot be matched to a name in the address list for a valid user - Exchange 2010

In some cases, I hide old users in Exchange Management Console so they don't appear in the global address list.  I had done that with a certain user, and I kept trying and trying to no avail to configure his Outlook.  I kept getting "The name cannot be matched to a name in the address list for a valid user."  I could log in to webmail for the user, and I could log on to a laptop as the user with no trouble - but Outlook could not find the user during mailbox setup/configuration.

The error:

The solution (uncheck "hide from Exchange address lists")