Fun with dead search engines

$CLIENT’s new site launched today at their new domain, which matches their name. The reason that it’s their new domain and not their current is because they only recently acquired the domain name. It had been dead for a while, but it previously housed a search engine.
I was watching the stats thinking Wow, they’re extremely popular when I realized that a disproportionate number of those requests were coming to 404 URLs. As it turns out, a lot of tools out there still think that this search engine (which has been dead for about 4 years) was still there, ready to search or whatever. I’m seeing searches from multi-searches and forms embedded in ugly web sites and I’m seeing URL submissions from site submitters that have probably never heard of Google.
The short term solution is to make the 404 page as low bandwidth as possible, but it may come to blocking people coming to known-bad URLs.