Easy way to do this is to just repopulate the Autocomplete list.
Import the users Windows Address Book.
Disconnect the PC's network cable.
Create a new message, hit the "To" button, select ALL contacts.
Send the message. This populates the autocomplete list with all the contacts.
Goto Outbox and delete the message.
Reconnect the network cable.
Works a treat. You can also repopulate the CC and BCC fields while you're at it.
Cheers.