Yappy non vedo la query.

puoi procedere direttamente con il delete e verificare con www.php.net/mysql_affected_rows se effettivamente hai cancellato qualcosa oppure fare le due cose distintamente

1.
codice:
$sql = "DELETE FROM utenti WHERE email='{$_REQUEST['email']}'";
mysql_query($sql) or die("Errore nell'esecuzione della query: $sql
".mysql_error());
$check = mysql_affected_rows();
if($check > 0) {
     echo "Cancellazione di $_REQUEST['email'] effettuata con successo";
} else if($check == 0) {
     echo "$_REQUEST['email'] non trovata";     
} else {
     echo "Errore nell'esecuzione della query";
}
2.
codice:
$sql = "SELECT 1 FROM utenti WHERE email='{$_REQUEST['email']}'";

$result = mysql_query($sql) or die("Errore nell'esecuzione della query: $sql
".mysql_error());
$num = mysql_num_rows($result);
if($num > 0) { // sono presenti record, procedi alla cancellazione
     $sql = "DELETE FROM utenti WHERE email='{$_REQUEST['email']}'";
     mysql_query($sql) or die("Errore nell'esecuzione della query: $sql
".mysql_error());
     $check = mysql_affected_rows();
     if($check > 0) {
         echo "Cancellazione di $_REQUEST['email'] effettuata con successo";
     } else if($check == 0) {
         echo "$_REQUEST['email'] non trovata";     
     } else {
         echo "Errore nell'esecuzione della query: $sql";
     }
} else {
     echo "$_REQUEST['email'] non trovata";     
}