Similar case here... I've seen this happening with WFs for which there is no reason email address would not be resolved and this error was triggered only few times so far... moreover, if related action / WF was re-initiated, email was delivered as expected!
On the other hand there were some users (in same AD OU) to whom no email notification could not have been delivered no matter what (in scope of same library WF of course)!
We're having the same issue here.
It seems that if an Active Directory user is found for the given email address for sending the email, it will consider it as a user instead of an external email address.
But if that AD user is disabled, the error "Failed to send message. Cannot get the full name or e-mail address of user" will occur .
In my opinion, that's a bug. Nintex team, could you please fix it?
The only workaround I found is to remove the email adress from the AD user, so it won't match it.
Thanks and regards.