I too had this problem when moving from Win 2k to Win XP. I had over 40 contacts and was determined not to have to break out the pen and paper.
Number 1 thing to know is Outlook XP seems to store the addresses in the PST file now. Not sure why but whatever. :-)
After lots of tinkering I found this to work. After setting up Outlook on your new system go in and import your PST file. You may or maynot have to resetup your email accounts, can't remember. It should import all your mail, AND most importantly your Contacts.
If this didn't help try the Knowledge Base. This article stuck out when I visited there.
http://support.microsoft.com/search/preview.aspx?scid=kb;en-us;Q291618
