I have a user that can add contacts, however they disappear after they've been added.
She is using Outlook 2010 and Windows XP.
The steps she follows are
Click on New Mail
Click on To
Type in a name and right click on it
Click on Add to Contacts
Save & Close