Correct me if I'm wrong, but don't new nodes have to be approved before they are visible? I often see "node approved by X" in my nodelet over there.
By default, you could make all new accounts unable to post comments on existing nodes until they've had a new node of their own approved. That would weed out all but the most dedicated spammers without forcing more work upon the admins. This isn't a fully automated solution, but it also wouldn't impact the legitimate users of this site in a negative way.
Update:
To address the first-post re-post BrowserUK brought up, you could also require some nominal amount of XP (or node reputation) before allowing the user to comment.