Have, in the past, complaints to ISPs (about stuff like this, not death threats, copyvios, or kiddieporn) been effective?

I'm not aware of them being used in the past. However, I'm told that most of the IPs being used at the moment are actually open proxies.

I figure what the vandalbot is doing is perfectly legal, isn't spam, and probably doesn't rise to the level of DOS

(IANAL) It isn't legal, because it's unauthorised use of a computer system, which is typically against anti-hacking legislation in most countries, including the USA. Anti- hacking legislation has been successfully used against people who have "hacked" by guessing URLs, so defacing a wiki should be cut and dry. It also falls into the category of a DOS, I reckon, though of course that's subjective.

No doubt JamesDay or Alex756 wll be able to explain why I'm wrong on the legal issue.

-Martin