php seo 404 error in webmaster tool

Question

 I have a PHP site that has 1000s of pages, and I delete some pages every day that has been indexed by google.  If a visitor comes to one of the pages I have deleted, they will be taken to the "search for related contents " page.

The code I use : 
if($deleted = true){
    header("HTTP/1.1 301 Moved Permanently");
    header("Location: /products-search.php");
    exit(); 
}

In the Google webmaster tool, I am getting a lot of soft 404 errors for the pages of this type. the message says: The target URL doesn't exist, but your server is not returning a 404 (file not found) error. Learn more

I don't want the user to get 404 error. Any solution ?