RUS is not updating addresses after a name change

This is how RUS should work::

"Determining What Action to Take on a Specific Object
When the Recipient Update Service is started by its schedule or by Update Now, the way it decides what to do on any particular object is exactly the same:

1.
 First, the Recipient Update Service determines which recipient policy to apply to the object. To do so, the Recipient Update Service sorts the list of policies and selects the policy with the highest priority that has a filter which applies to this object and that is not present in the msExchPoliciesExcluded attribute on the user. In other words, the Recipient Update Service selects the highest-priority non-excluded policy that applies to the user. When the choice is made, the Recipient Update Service stamps the objectGUID attribute of that policy into the msExchPoliciesIncluded attribute on the recipient.
 
2.
 Second, the Recipient Update Service determines whether the recipient is new. If the recipient has no proxy addresses, then it is considered to be new and the Recipient Update Service stamps the recipient with all the checked addresses on the policy. The "to do" list does not play any role in the stamping of new recipients.

If the recipient is not new, the Recipient Update Service consults the "to do" list:

a.
 If any of the primary addresses for this policy are populated in the gatewayProxy attribute of the Recipient Update Service and the addresses that are currently on the object do not match the policy, the Recipient Update Service regenerates those primary addresses. The previous primary address becomes a secondary address.
 
b.
 If any secondary addresses that are listed in gatewayProxy do not already exist on the recipient, the Recipient Update Service adds those secondary addresses to the recipient.
 
c.
 If any address type is set for removal in the "to do" list, the Recipient Update Service removes all addresses of that type from the recipient.
 

When all steps in the "to do" list are complete, the Recipient Update Service continues with the next step.

Note In Exchange Server 2003 Service Pack (SP1), a new GUID was added that will cause the Recipient Update Service to act as if the policy is applied for a specific recipient. If the MSExchPoliciesIncluded attribute on the recipient contains the value {23668AD4-4FA1-4EE8-B2BB-F94640E8FBA0},{26491CFC-9E50-4857-861B-0CB8DF22B5D7}, the Recipient Update Service will perform steps 2a and 2b just as if the gatewayProxy attribute were populated with the proxy addresses from the policy that matches the recipient."

Link:http://support.microsoft.com/kb/328738

Thanks, Computer_Geek

OK, the problem I have falls into category 2a in your list.  I checked the gatewayProxy attribute for the policy in question & it has "SMTP:%g.%s@company.com", so it should notice that the user's SMTP address no longer matches that pattern & update the primary SMTP address.

I went through the steps of creating a new user in our testing environment (seperate forest) & got exactly the same issue - When I altered the surname, the email addresses would not update. I did an "UpdateNow" on the RUS and a "Rebuild" on the RUS with no effect. I also did a re-apply to the specific policy - no effect.

it seems like the change in the user's surname is not getting flagged & the RUS is happily passing over it.
What else can I check?

Sorry, that should have been "Exchange_Geek" above!

UPDATE: The "rebuild" option does update the email addresses in the manner it is supposed to.
However, my live environment has several thousand users & I can't run Rebuild there too often.
Still looking for why it doesn't notice the change in surname.

Thanks for your assistance, Exchange Geek. Sorry for the long delay in accepting. I have been run around & this problem has been bumped in priority. Since I won't be coming back to it any time soon, you at least deserve the points , as the fault for lack of resolution is mine.
Cheers,