The problem is that a DELETE query always returns TRUE, as long as the query was formally OK. From the PHP manual:
A non-FALSE return value means that the query was legal and could be executed by the server. It does not indicate anything about the number of rows affected or returned. It is perfectly possible for a query to succeed but affect no rows or return no rows.
What you need is [url=http://www.php.net/manual/en/function.mysql-affected-rows.php]mysql_affected_rows()[/url], After a DELETE query it returns the number of deleted rows, and obviously 0 if no row has been deleted. This should do the trick.