The NK2 file uses the x.500 address to resolve names in Exchange. So, you need to make sure each mailbox has an x.500 address that matches the address on the old domain.
I'm pretty sure (no access to Exchange server right now) that you can add multiple x.500 addresses to a mailbox. If you can, simply copy the LegacyExchangeDN attribute from the old mailbox and add it as a new x.500 address on the new mailbox. (To add a new x.500 address, select the "custom address" and specify the address type as "X500" (no quotes)).
If you can't add a second x.500 address, then create a contact for each user, modify the x.500 address for the contact, and then set the contact to forward all mail to the new mailbox.
Hope this all makes sense. Good luck...