Използвайте
INSERT IGNORE INTO Users VALUES(...);
с уникален ключ в полето за имейл, след което проверете броя на редовете с mysql_affected_rows();
Това ще доведе до единична заявка към БД и ще изключи условието за състезание на времевия прозорец между SELECT и INSERT