Thank you all for your answers. I'll try them on the real data tomorrow and see which performs the quickest.

A couple of other questions ... If I stick with #tblNoEmail as just having one column - EmailAddress - what sort of index should I put on it?

And I will need, wherever a list of email addresses is displayed in the front end, to highlight any email addresses that are in #tblNoEmail

I could do this ...(or similar using the CTE solution above)

SELECT

e.EmailAddress, CASE WHEN ne.EmailAddress IS NOT NULL THEN 'No' ELSE 'Yes' END AS [CanUseEmailAddress] FROM #tblContacts c
JOIN #tblEmails e ON c.ContactID = e.ContactID
LEFT JOIN #tblNoEmail ne ON e.EmailAddress = ne.EmailAddress;

Is there a better way to do that?