Thanks for the information, Laugh. The ban plugin is very useful and I will consider using it for a few sites. However it is not eliminating the 404's.
Like the login limits hacking of user/pass by introducing a delay after a failing entry, I merely think of a similar technique: catch the 404 and present further requests (all !) with a message saying that the user has to wait for some time to issue the next request and that the attempt is logged.
Remember this is only for anonymous users 'typing' the url in the address bar of the browser: there is no cookie or no referer, while it is the third attempt with 10 seconds.
Note that some attacks already fake the referer with either invalid url, either valid ones.
Is the example from login-flood protection suitable for duplicating?
Another approach to invoke a delay could be a captcha in the 404 response, saying 'please ignore this error'. Any other suggestions?