Hi Graeme,
Since email addresses must be unique across all Workfront domains, and you cannot find it within your domain but get an "already in use"' error when you try to update an existing user's email to that exact email address, it is possible that the enail is in use in a different Workfront domain.
In order, I suggest you:
try a "forgot password" using the desired email; if the account is active and it does come through to its owner, have them log in to wherever it takes them (ehm...which, technically, would be a type of security breach into the "other" domain...hmm...let's table that discussion until such a breach is confirmed), and then edit their email in the other domain to Something Else, thereby freeing up the desired email for use in your domain
If that doesn't work, exploit the fact that emails are case sensitive and capitalize some or all of the email (in consultation with the real user: spelling counts) so they can get in and you can move on
contact support, as Eric suggested; in any case, I suspect they'd appreciate studying this one carefully
Regards,
Doug