Gathering required information

When was the object created
How many Domain are there and how many Exchange Servers
Have we created a New recipient policy?
Are we able to see RUS object in Exchange System Manager
Is the Exchange System Attendant service running (RUS is a task of System Attendant)
Was any Domain Controller Decommission and if yes was it done forcefully

Troubleshooting steps

There are 2 types of Recipient Update Service
1.Domain RUS
2.Enterprise RUS

Domain RUS stamps objects in the Domain Partition
Enterprise RUS will stamp objects in the Configuration partition in AD (So now you know which RUS to troubleshoot and when)

If there are Multiple Domains and we have single Exchange Server only in a Domain we need to run DomainPrep on all other Domains where Exchange Server is not installed in order for RUS to stamp the User
We need multiple Domain RUS if we have Users located in different Domain wher Exchange Server is not installed

1.Open the RUS and Check whether the Domain Controller (GC is preferred) and Exchange Server listed there are up and  running and can we communicate successfully

2. Click on the browse button for both the RUS and  see do we get any errors if yes we are not able to communicate with
    the servers properly (trying to access the server using Netbios name)
    Try to ping to the Server by IP Address, FQDN, NetBIOS (important) if not (try below step otherwise skip and go to step 4)

3. Add an entry in the Host file for the Server you are getting error and then run the below command from the command
    prompt (this is a workaround)
         Ipconfig /flushdns
         Ipconfig /registerdns
         Nbtstat /R (To purge and preload the NBT remote cache table)
         Nbtstat /RR (To refresh the NetBIOS name registered)

4.If a new recipient policy has been created have we applied it?

5.Check the Recipient Policy do we have any third party address given over there such as a fax connector address if yes do
   we get any error in the app logs

6.Create a New test User and Check does the RUS stamps this User If yes then check the User which is not getting
   stamped does it has Allow inheritable from parent to propagate this object and all child object selected. If this is not
   checked RUS will not stamped the User as RUS does not have appropriate permission to change the user attributes you
   could see that if you create a new User is stamped but the old user will never get stamped by RUS even though if the old  
   user USN is high or you manually make any changes to the User and make the USN always high then the New user

7.Enable Diagnostic Logging on the exchange Server which is specified in Recipient Update Service for the following counters.

          MSExchangeAL\LDAP Operations
          MSExchangeAL\Address List Synchronization
          MSExchangeSA\Proxy Generation (Exchange 2003 only)

8. Then try to update the appropriate RUS,Check whether the User is stamped if not check the Application Log on RUS 
    Server are there any events for MsExchangeAL if  not we need to restart the System Attendant Service in order  
    for RUS to stamp Users or If we have multiple exchange Server point the RUS to a different Exchange Server or a GC and
    then run Update Now on the RUS

9. If still the User is not stamped checked for the below event

Event Source: MSExchangeAL
Event Category: LDAP Operations
Event ID: 8011
Description:
Searching directory bilongexch1.bilong.test at base
'DC=bilong,DC=test' using filter'(&(USNChanged>=273870)(uSNChanged<=298312)((objectclass=*)))' and requesting attributes distinguishedName; objectGUID; LegacyExchangeDN; msExchADCGlobalNames; ObjectSID; ObjectClass; objectCategory; displayName; msExchHideFromAddressLists; hideDLMembership; ntsecuritydescriptor; showInAdvancedViewOnly; msExchALObjectVersion; showInAddressBook; msExchPolicyEnabled; givenName; sn; cn; mailNickname; targetAddress; initials; proxyAddresses; mail; textEncodedORAddress; msExchHomeServerName; msExchExpansionServerName; msExchCustomProxyAddresses; msExchPoliciesIncluded; msExchPoliciesExcluded; replPropertyMetaData; replicatedObjectVersion; ReplicationSignature; WhenChanged; WhenCreated; USNchanged; USNcreated; ObjectVersion; isDeleted; homeMDB; homeMTA; msExchMailboxGuid; msExchMailboxSecurityDescriptor; msExchResourceGUID; UserAccountControl; msExchUserAccountControl.

10.You will have number of 8011 events the best way to find the event with this description is right clicking on the Application 
   Log click on find and in the Description type USNChanged this will take you to the 8011 event with above description
   Check the USNChanged value then using LDP or ADSIEDIT check the USN value for the user if the USN value of the User is 
   lower then the USNChanged value showed in event 8011 make some changes to the user such as adding a description and
   then again check the USNChanged value this time it should be higher and the next time you do a Update Now on the RUS
   the user should have been stamped by RUS If the USNChanged value of the user is high then the USNChanged value in 
   the description of event 8011 that means that RUS is still catching up with that User and the user will be stamped.
   If the Customer has run rebuild and if there are thousand of users then the RUS will take a lot of time to stamp new users 
   as when you run rebuild against RUS it starts from USNChanged 1.

How to identify if rebuild was run against Recipient Update Service.

One way to check for a Rebuild is to use the repadmin tool from the Windows 2000 Support Tools. Use ADSI Edit or LDP to get the distinguished Name of the RUS you are troubleshooting. Then, from a command line, run:
 
        repadmin /showmeta "<distinguishedName of RUS>" >rusmeta.txt

The resulting text file will contain a list of properties on the RUS object. Find the line corresponding to the msExchDoFullReplication property:
 When an admin chooses Rebuild, msExchDoFullReplication is set to TRUE, and the RUS later sets it to FALSE after the Rebuild kicks off. By looking at the timestamp shown in the repadmin output, you can see when this attribute was last changed, and thus when a Rebuild was last run.

Note that running a Rebuild usually is not useful for troubleshooting. The only difference between a Rebuild and an Update Now is that Rebuild causes the RUS to start over from a USN of 1. Update Now starts from the highest USN last recorded by the RUS, which is stored in the msExchServer1HighestUSN property on the RUS object in the Active Directory. So if the RUS is not working as expected against new or modified objects (the objects that would be touched by an Update Now), running a Rebuild will not help. Because of the time it can take for a Rebuild to complete in a large environment, carefully consider how much time it will take to resume normal RUS operation before you choose to do a Rebuild. Once a Rebuild has started, you must wait for the RUS to catch up before you can do any useful troubleshooting against new

If all the above steps have not resolved the issue check below permissions on the object or on the OU where the object located

The following permission are required for the Exchange Enterprise servers group on an OU so that the users in that OU are stamped by Recipient Update Service (These are Special permission)

Group: Exchange Enterprise Servers Group
Applies To ": This Objects and all Child Objects
Permission Given: List Contents, Write Properties

Group: Exchange Enterprise Servers Group
Applies To ": User Objects
Permission Given: Read All Properties, List Contents, Read Permission

Group: Exchange Enterprise Servers Group
Applies To ": Groups Objects
Permission Given: Read All Properties, List Contents, Read Permission

Group: Exchange Enterprise Servers Group
Applies To ": InetOrg Person Objects
Permission Given: Read All Properties, List Contents, Read Permission

Related Knowledge Base Article

288807:Troubleshooting the Recipient Update Service in Exchange Server 2003 and Exchange 2000 Server
328738:How the Recipient Update Service applies recipient policies
255719:XADM: Description of Exchange 2000 Server Recipient Update Service
253770 Tasks performed by the Exchange Recipient Update Service
319201:How To Use Recipient Policies to Control E-mail Addresses in Exchange 2000