Il modo più rapido per verificare la presenza di record preesistenti prima di inserire [mysql_errno()]

Usa

INSERT IGNORE INTO Users VALUES(...);

con una chiave univoca nel campo e-mail, quindi controlla il conteggio delle righe con mysql_affected_rows();

Ciò risulterà in una singola query al DB ed escluderà la race condition della finestra temporale tra SELECT e INSERT