Usar
INSERT IGNORE INTO Users VALUES(...);
com uma chave única no campo de email, então verifique a contagem de linhas com mysql_affected_rows();
Isso resultará em uma única consulta ao banco de dados e descartará a condição de corrida da janela de tempo entre SELECT e INSERT
