Through all the noise, what is easy to overlook is the root of this problem.
It's not about letting bots in or out... well, ok, it is about that, but their aggressive behaviour and refusal to obey robots.txt is the problem here. Any time you start checking referals you have opened the door once again to unruly, disobedient web bots.
I think scaling one reason that so many of us see this as a problem with a simple solution. Our sites don't have the massive bandwidth issues.
The only real solution is to add a site search.