For a boolean column, "0" will definitely give you the "Data type mismatch in criteria expression" error. However, 0 or False without quotes should work. I don't understand why they are generating the same error.
See if you can produce a working query by editing the SQL directly. Create a new query, switch to SQL View and paste in this statement (replacing YourTableName with the name of your table).
SELECT IsValidEmail([E-Mail]) AS valid_email
FROM YourTableName
WHERE IsValidEmail([E-Mail]) = False;
Will your query run without error when you create it that way?
Update: Since that query also produced the same error, all I can suggest is trying this one without any criteria.
SELECT
IsValidEmail([E-Mail]) AS valid_email,
TypeName(IsValidEmail([E-Mail])) AS type_of_valid_email
FROM YourTableName;
However, that seems like a long shot because you already told us your earlier attempt without criteria ran without error. If this doesn't identify the problem, would you consider emailing me a stripped down copy of your database? Let me know if you're interested and I'll give you my email address.