Well I appear to have the comment spam situation under control. I installed Spam Karma 2 as Miles suggested and so far so good. I am still getting comment spams but they all appear to be getting caught. I refuse to turn comments off or to make people register as I think this discourages people from leaving comments. I quite like this idea although I am not sure how well it will work if spammers specifically target your site because it has lots of traffic, as suggested in some of the comments. Still, it may be worth a try.
Another option would be cut the spammer out at the transport level: if a machine with a blacklisted IP address tries to make a connection, just drop it. This would avoid the need to have fancy filters that try and figure out statistically whether something is spam or not.
The battle is won but the war is not over! Ding ding. Round 2.