A robots.txt could easily be set up to disallow /wiki/special%3ARecentChanges (and various case variations). That only stops _nice_ spiders, of course.
History links would need to be changed to be sufficiently distinguishable, for instance using /wiki.phtml?title=Foo&action=history etc; then ban /wiki.phtml.
I think we should do that ASAP. Let's close the whole special: namespace, &action=edit, &action=history, &diff=yes and &oldID stuff to spiders. None of this is of any value to the spiders anyway.
Axel