Googlebot & Could not find valid value for id
Just speculating here, but seems like google is getting the links either from the pages and/or some unknown static web pages.

A possible, but not so great solution is:

a. Create and register a new CiviCRM fatal handler

b. If you detect the user agent is googlebot and/or some other friendly search engines, redirect to main page of site, maybe with a CMS message

c. If not, keep fatal message as is (unless you want to redefine this also)