Använd
INSERT IGNORE INTO Users VALUES(...);
med en unik nyckel i e-postfältet, kontrollera sedan antalet rader med mysql_affected_rows();
Detta kommer att resultera i en enda fråga till DB och utesluter tävlingsvillkoret för tidsfönstret mellan SELECT och INSERT