However that file that holds those addresses can be moved rather easily. This file is a *.N2K file. It will live in the user's profile folder.
Under Vista, the file is generally located in this folder:
and XP would have it here:
C:\Documents and Settings\
If multiple outlook profiles exist, you will have N2K files with corresponding names.
Just copy the user's N2K file over the new one on the new machine, and you should be good to go.