The Directory Exchange feature will copy the cc:Mail users into the Notes N&A Book. However, it will not generate a Lotus Notes fully qualified name. Edit the user document in the Notes N&A Book so it uses the fully qualified Notes name. Then, add the Notes user.
If you get a duplicate and you delete the user name in the N&A Book, the deletion will get propagated back into the cc:Mail user list. This is a bad thing to do.