La sentencia "DELETE FROM tabla WHERE campo=valor" se ejecutará de todas maneras y si no hay ningún registro que cumpla la condición, pues no eliminará nada... pero tampoco devolverá error.
para saber cuántas filas fueron afectadas con una sentencia como DELETE o UPDATE utiliza la función
mysql_affected_rows() Código PHP:
mysql_query("DELETE FROM tabla WHERE campo='valor'");
$filas_eliminadas = mysql_affected_rows();
echo 'Filas eliminadas :: '.$filas_eliminadas;
Saludos