Weird 404 errors on search

Hi all,

I have a bizarre problem in one of the WP installs I manage. We have Webmaster tools set up, and in there we are getting 1000s of 404 errors reported, all of the same format:

http://www.domain.com/wordpress/page/36?s=keyword

Where the search for “keyword” doesn’t have that many pages. To make matters even more confusing, the page is linked from another instance like this – same link structure, another 404, where the page is higher than the search goes to. Sorry if that’s confusing!

I am using the plugin WP Pagination, not sure if that is causing it. I have this plugin on other sites which don’t have these errors, so I don’t think it is, but could still be related.

Has anyone ever seen this before? It’s just so bizarre… neither the linked page, nor the linked-from page exist… so how are these 404s even happening??

If anyone can shed some light I would be grateful.