Well, I tried the IP banning approach. We'll see how it goes.
One thing though: We're on 7.2.2, and at one point I was seeing a bunch of twiceler requests in the accesslog, but I don't see anything other than google, msn, and yahoo in the spider list on the who's online page. Is this because of our version being slightly older or does cuil do something different to simply show up as an anonymous user?
Also, I noticed from our logs that they're using the 38.99.44.x subnet as well, so I added that.