My first suggestion is to try a different captcha. There are quite a few that can be solved algorithmically.
The next step is to have a 'bad word' list. If the words are contained anywhere within the message body or subject, delete them and block the IP. My block list has thousands of IPs. If you can automate the process, that will help.
There are tons of things a person needs to do in order to combat spam; I am getting ready to implement comments on a web site I am working on, so your problem is timely in that it is making me think of a few things. My plan contains some of the same elements as yours; ip based logging and blocking, approving comments, etc. I am also going to require that the user be logged in with a valid email address. I will be implementing a bad word list, and spam databases. I have not yet decided if I am going to use something off the shelf, or if I am going to roll my own. I don't mind using other people's libraries, but it seems that every time I do, they update the library and fail to maintain backwards compatibility. Rolling my own means that at least I know what is going on, but it takes time.
"Take the risk of thinking for yourself, much more happiness, truth, beauty, and wisdo
m will come to you that way" - Christopher Hitchens