Outlook has a nicknames function.  This is when you start typing the email address in the TO box and Outlook automatically offers email addresses you have already used.

If emails fail when you try to send using this function you will have to delete the existing nickname and try again.  Microsoft has published an article how to do this with various versions of Outlook - http://support.microsoft.com/kb/287623

Below are details taken from Microsofts article:

How to remove nickname cache entries, one at a time

Outlook 2010

1. Open a new email message.
2. Type the first few characters of the nickname cache entry that you want to remove from the cache.
3. When the entry appears in the "suggested names" list, move your mouse pointer over the name until it becomes highlighted. (But do not click the name).
4. When the “X” icon appears next to the highlighted name, click X to remove the name from the list.

Outlook 2007 or Outlook 2003

1. Open a new email message.
2. Type the first few characters of the nickname cache entry that you want to remove from the cache.
3. When the entry appears in the "suggested names" list, use the UP and DOWN arrow keys on your keyboard to select the entry, and then press DELETE on your keyboard.

How to clear the whole nickname cache

Outlook 2010

Use one of the following methods to reset the whole Outlook nickname cache for Microsoft Outlook 2010. 

Method 1

1. With Outlook 2010 open, click File (BackStage), and then click Options.
2. Click the Mail tab.
3. Under Send Messages, click Empty Auto-Complete List.

Outlook will generate a new nickname cache.

Method 2

1. Click Start, and then click Run.
2. Start Outlook by using the /CleanAutoCompleteCache switch.
   
   For example: Outlook.exe /CleanAutoCompleteCache
   
   Note If Outlook is not installed in the default location, you must point to the path of Outlook.exe. 

Outlook will generate a new nickname cache.

Outlook 2002 through Outlook 2007

Windows 7 or Windows Vista: Use the following steps to reset the whole Outlook nickname cache.

1. Exit Outlook.
2. Click Start, and then click click Computer.
3. Click Organize, and then click Folder and search options.
4. On the View tab, click to enable the Show hidden files, folders, and drives option.
5. Click OK.
6. On the Start menu, click All Programs, click Accessories, and then click Run.
7. In the Run dialog box, type the following command (including the quotation marks), and then click OK:
   
   “C:\ Users\UserName\AppData\Roaming\Microsoft\Outlook”
   
   Note Username in this path is the name of the currently logged on Windows user.
8. Right-click the .NK2 file that has name of the profile that you want to reset, and then click Rename. 
9. Rename the file as profilename.bak, and then press ENTER.
10. Start Outlook.
    

 Windows XP: Use the following steps to reset the whole Outlook nickname cache.

1. Quit Outlook.
2. Click Start, and then click Search.
3. In the Search Companion left-side panel, click All files or folders.
4. In the All or part of the file name: box, type *.NK2.
5. In the Look In box, click to select your local hard disk.
6. Click More advanced options, click to select Search hidden files and folders check box.
7. Click Search.
8. Right-click the .NK2 file with the name of the profile that you want to reset, and then click Rename.
9. Rename the file to profilename.bak, and then press ENTER.
10. Quit Windows Explorer.
11. Restart Outlook.

Outlook will generate a new nickname cache.

Use the steps in the following section to reset the Outlook nickname cache for both Microsoft Windows 2000 and Microsoft Windows Millennium Edition (Me).

1. Quit Outlook.
2. Start Windows Explorer.
3. On the Tools menu, click Folder Options, and then click the View tab.
4. Under Advanced Settings, click to select the Show hidden files and folders check box.
5. Click OK.
6. Click Start, point to Search, and then click For Files or Folders.
7. In the Search for Files and Folders box, type *.NK2 in the Search for files or folders named box.
8. In the Look In box, click to select your local hard disk.
9. Click Search Now.
10. Right-click the .NK2 file with the name of the profile that you want to reset, and then click Rename.
11. Rename the file to profilename.bak, and then press ENTER.
12. Quit Windows Explorer.
13. Restart Outlook.

Outlook will generate a new nickname cache.

Use the steps in the following section to reset the Outlook nickname cache for both Microsoft Windows NT 4.0 and Microsoft Windows 98:

1. Quit Outlook.
2. Start Windows Explorer.
3. On the Tools menu, click Folder Options, and then click the View tab.
4. Under Advanced Settings, click to select the Show all files check box.
5. Click OK.
6. Click Start, point to Search, and then click For Files or Folders.
7. In the Named box, type *.NK2.
8. In the Look In box, click to select your local hard disk.
9. Click Find Now.
10. Right-click the .NK2 file with the name of the profile that you want to reset, and then click Rename.
11. Rename the file to profilename.bak, and then press ENTER.
12. Quit Windows Explorer.
13. Restart Outlook.

Outlook will generate a new nickname cache.