I have been getting a lot of comment spam on this blog. I've just removed over 20.000 comments from the database. Apparently WordPress still stores the comment if you mark it as spam. I haven't looked in the code if it uses this for some clever techniques to detect future spam. Right now I just wanted to clean up the database because I'm going to upgrade to WordPress 2.
The following website has listed two MySQL commands. One with which you can count the amount of spam and one to remove all the spam-comments:
Count the amount of comment types:
select count(comment_ID), comment_approved from wp_comments group by comment_approved;
Remove all spam comments:
delete from wp_comments where comment_approved = 'spam';
Source: http://www.makeyougohmm.com/20061207/4025/