Vari modi, p.es.:
1) in un array metti tutte le mail da controllare, poi fai un ciclo (foreach) e dentro una SELECT per controllare se ciascun elemento è presente o meno nel db
2) in un array metti le mail da controllare, in un altro quelle che hai già: applichi una funzione di "differenza" tra vettori (es.: array_diff) e "in un colpo" hai l'elenco delle mail "mancanti"
3) ...
P.es. il punto 2: per mettere in un array tutte le mail del db basta una "SELECT *" e poi un ciclo sui risultati.