Core Issue
After a new subscriber is created in Exchange, when you search for that new subscriber in Cisco Unity, it does not show up. A wild card search using * only shows the old subscriber.
Resolution
In order to resolve this issue, first make sure that all permissions on the Exchange are good. Refer to Exchange Permissions Required for the appropriate set of permissions.
This issue occurs because Cisco Unity tags these subscribers such that at the next import, it looks at the attributes and if they have been tagged, they do not show up for import. For Exchange 2000 and 2003 you can use the Remove Subscriber Properties Tool to remove these. However, for Exchange 5.5 you must open Exchange in raw mode (use the -r option on the Exchange administrator) and remove custom attributes 12 and 14 from the subscriber.
For more information, refer to the Exchange 5.5 Directory section of Cisco Unity Data and the Directory (All Versions with Microsoft Exchange).