This is frustrating sometimes, a manual sync doesn't always make the mailbox come up. When I get this now I just use an EVPM script to enable them:
DirectoryComputerName = 'KVS Server'
SiteName = 'Your KVS Sitename'
DistinguishedName = /O=whatever/OU=HGH CC VA/CN=RECIPIENTS/CN=WHOEVER
Name = mailboxroot
Enabled = true
As long as you can get the DN of the user it will find them. Or just set it to all and enable the entire Exchange server in one shot (I typically run this after I enable an entire server just to make sure no users missed getting enabled).