I used to copy the whole directory over for ICQ and then do a new install over top of it when I was in Win98.
I am not at my home machine now to see where the contacts are in but there should be a long list with uin numbers that are your contacts. If you don't include these where the new install of icq occurs then you would have to get people to authorize your adding them to your contact list for those that have it set to authorize.
I'm not sure about how this would work with Win2000/XP but I would try that there too and see if it works.