If you mean new addresses as in the Suggested names from email history. The NK2 file may have gotten corrupted. That is the file that contains email address history for Outlook. It is located in C:\Documents and Settings\UserName\Application Data\Microsoft\Outlook.
1. Close Outlook
2. Renamed the NK2 file to something like NK2.old or delete it.
3. Re-open Outlook
4. Check if the new email addresses are being saved.