I've meaning to write this for a while, but not had a lot of spare time recently.
With Exchange 2010 RU6 Microsoft added a "feature" by "design" - three extra random characters on the end of a users nickname too supposedly ensure uniqueness within the forest... we've survived until now without this uniqueness Microsoft, why the sudden shift? - That said you won't notice it if you're using an up-to-date Outlook client, however Outlook 2003 uses this specific attribute in the AD called legacyexchangeDN, which is how the nickname cache (NK2 file) is populated for local exchange users in the same exchange forest.
I managed to find the problem within the legacyexchangeDN using good old fashioned snooping around the AD attributes with adsiedit
Unfortunately not all companies can afford a migration from Outlook 2003 & non-exchange mail server to Outlook 2010/2013 & Exchange 2010/2013 for hundreds of users and this "feature by design" isn't exactly something you would anticipate from Microsoft...Call me cynical, but this seems like a deliberate change to get people to upgrade Office...
Things I learnt when looking into this, don't rename or delete the content within this attribute as any cached addresses will not receive the email and the sender will get an NDA, you'd have to rebuild every single NK2 file for all users - not a quick or easy task and would be time consuming (considering they're moving to a new version of Office soon, it wasn't much of a decision). So as it doesn't effect anything in real terms, its best to put up with the nicknames with 3 random characters on the end until you can get them upgraded to a newer Outlook client.
Thankfully the client was understanding that it was a unique configuration with the view to upgrade Outlook later on.
Reference:
http://social.technet.microsoft.com/Forums/en-US/exchange2010/thread/8b4181c3-2fa2-4311-a245-3e81e9659f4b
http://social.technet.microsoft.com/Forums/exchange/en-US/ccd65438-814f-4b5c-ae3e-2a0fd110981a/part-of-legacyexchangedn-in-outlook-2003-autocomplete-list