HTTP 404 Header

There is no HTTP 404 header called on the search404 page. This is critical because it means search engines can find any address with your base URL and index it. For example, http://www.example.com/ajfdsaoiewjfghzxcm could be indexed.

You can use drupal_set_header("HTTP/1.0 404 Not Found"); to set the HTTP header to 404. Add it as the first line in function search404_page().