PHP SEO 404 error in webmaster tool, avoid 404 for redirect

I have a PHP site which contains 1000s of pages... Every day I delete 10s of pages which already indexed by GOOGLE...

When visitor come to one of those pages I do check to see if it is deleted or not... If deleted I redirect the user to the search page to start search for similar contents...

I am using this code:

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

the problem that in GOOGLE webmaster tool I get a lot of soft 404 errors for the pages of this type. the message say:

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... I need him to go to search page...

How to solve this?

You should still return a 404 unless you expect to put that page back up later. A redirect is a bad idea for SEO in this case.

What you could do is return a 404 in the header but show the search page anyway:

<?php

header("HTTP/1.1 404 Not Found");

echo "The page you're looking for doesn't exist or was deleted. You can use the search below to find more...";

// include search box here