Outlook using OU addressess instead of Email addresses

Can you paste the complete NDR?

I've got a better question. How recently did they upgrade their exchange server?
This thread sheds a little bit of light on the problem, and provides a fix: http://www.winserverkb.com/Uwe/Forum.aspx/exchange-admin/68262/Users-cannot-send-email-to-New-account

Basically, the user is, for some reason, attempting to send internal emails to users using the old legacy x.500 DN system. If this is the only user having this issue, it may be necessary to re-create the account and mailbox for them. If everyone is having this problem, you may need to follow the instructions in that thread for each user to resolve it.

You need to delete "corrupted" client cashed adress with NK2Edit
http://nirsoft.net/utils/outlook_nk2_edit.html
Run this tool on client and delete faik address.

is only this user facing issue or multiple user. first need to determine is the issue is at server side or the client server.
if this is client side, only for single user then DLSmlSS trick should work. else let us know for further .

The "upgrade" wasn't really an upgrade. We did a fresh, new, clean install of a server, used Exmerge to export their PST files, and then imported them using Outlook after it was connected to the domain and the account was setup.

DrDamnit, did you try my tip?

dISmISS:

These are Outlook 2010 clients with Exchange 2007 on the backend. MSOL no longer uses nk2 files, but rather uses the suggested contacts from the Exchange contacts folders.

Dismiss is correct. The exchange migration left some faulty information in the user's internal contact list. Instead of using the correct contact information for local users, the user is using cached information from the old Exchange server which is written in the x.500 format that the new Exchange server won't accept.

Thank you dISmISS & acbrown2010. I'll try that and get back to you.

Can this be done from Outlook 2003? I have OL2003 installed on a VM on the server (I used it to import the PST files to begin with). It would be great if I could do it from there because then it will just magically "work" for the users....

Used your answer to write a script. Thanks!

'Dim vars
        dim x,t,m,filename
        dim wsh
        dim fso
        dim d
        dim args
        dim OLPath
        dim WshShell
        dim WshSysEnv
        dim myLog

'Create objects
        set fso = WScript.CreateObject("Scripting.fileSystemObject")
        Set WshShell = WScript.CreateObject("WScript.Shell")
        set WshSysEnv = WshShell.Environment("PROCESS")
        Set args = WScript.Arguments

'Setup Temp Folder
        if not fso.FolderExists("C:\OLFix") then fso.CreateFolder("C:\OLFix")

'Setup Log File
        Set myLog = fso.CreateTextFile("C:\OLFix\OLFix.log")

'Setup Registry Objects

        dim oReg,strKeyPath
        const HKEY_LOCAL_MACHINE = &H80000002
        strComputer = "."
        Set oReg=GetObject("winmgmts:{impersonationLevel=impersonate}!\\" & strComputer & "\root\default:StdRegProv")

'Get current path for OL14 (2010)
        myLog.WriteLine "Looking for Outlook 2010..."
        strKeyPath = "SOFTWARE\Microsoft\Office\14.0\Outlook\InstallRoot"
        strEntryName = "Path"
        oReg.GetExpandedStringValue HKEY_LOCAL_MACHINE,strKeyPath,strEntryName,strValue
        if len(strValue) >0 then
                OLPath = strValue
                myLog.Writeline "Found Path: " & OLPath
        end if

'Get current path for OL12 (2007)
        if len(OLPath) = 0 then
                myLog.WriteLine "Looking for Outlook 2007..."
                strKeyPath = "SOFTWARE\Microsoft\Office\12.0\Outlook\InstallRoot"
                strEntryName = "Path"
                oReg.GetExpandedStringValue HKEY_LOCAL_MACHINE,strKeyPath,strEntryName,strValue
                if len(strValue) >0 then
                        OLPath = strValue
                        myLog.Writeline "Found Path: " & OLPath
                end if
        end if

'Find Outlook the old fashioned way to confirm it.

        myLog.Writeline "Program Files should be here: " & WshSysEnv("PROGRAMFILES")

        dim bConfirmed
        bConfirmed = false

        if fso.FileExists(OLPath & "outlook.exe") then
                bConfirmed = true
                OLPath = OLPath & "outlook.exe"
                myLog.Writeline "Outlook confirmed here: " & OLPath
        else
                'Loop through the possibilities.
                for x = 10 to 14
                        if fso.FileExists(WshSysEnv("PROGRAMFILES") & "\Microsoft Office\Office" & x & "\Outlook.exe") then
                                OLPath = WshSysEnv("PROGRAMFILES") & "\Microsoft Office\Office" & x & "\Outlook.exe"
                                myLog.WriteLine "Outlook confirmed here: " & OLPath
                        end if

                        if len(OLPath) = 0 then
                                myLog.WriteLine "Outlook could not be found. I cannot continue. Please contact your administrator for assitance."
                                quit
                        end if
                next
        end if

'Get User Profile Path
        myLog.Write "Working with Profile Path: "
        myLog.Writeline WshSysEnv("USERPROFILE")

'Set our target path
        dim fileTarget
        folderTarget = WshSysEnv("USERPROFILE") & "\AppData\Local\Microsoft\Outlook\RoamCache\"

'Check to see if the file is there...

        dim oFile
        dim oFolder
        dim oParts
        dim iCounter
        set oFolder = fso.GetFolder(folderTarget)

        for each oFile in oFolder.Files
                myLog.writeline "Checking: " & ofile.name
                oParts = split(ofile.name,"_")
                if oParts(1) = "Autocomplete" then
                        iCounter = iCounter + 1
                        myLog.Writeline "Found file! moving " & ofile.name
                        fso.MoveFile ofile.path, "C:\OLFix\"& ofile.name
                end if
        next

        myLog.WriteLine "Renamed " & iCounter & " files."

        myLog.WriteLine "Attempting to start Outlook..."

        dim cmd
        cmd = chr(34) & OLPath & chr(34) & " /cleanautocompletecache"

        myLog.WriteLine "Using: " & cmd

        WshShell.run cmd,1,true