For some reason I can no longer post a comment as an Anonymous user in my Drupal installation. I haven't tried in a while, so I'm not quite sure when this functionality was broken.
I have Services installed, and I can post anonymous comments using comment.save. I have altered the Input Formats if that could break something.
I have enabled both post comments and access comments on the anonymous user. The comments does not show up in the database. In fact, the native Drupal function comment_save isn't called when I try to comment as Anonymous (I check this by adding print_r($edit);die(); at the top of the comment_save function in comment.module. Also I read something that not having a User with the UID 0 would break the Anonymous commenting, this user exists (obviously, since commenting through Services works)
I have tried out the AntiSpam module, and posted a comment as Anonymous that would get caught(and did) in the spamfilter, but this module is now disabled.
I'm really running out of ideas here, does anyone have any other suggestions on what to do? In the meanwhile I'm going to attempt to backtrack the code to figure out why comment_save() isn't being called.
Edit: Anonymous users also don't have to submit email and such to post, if that matters in any way.
By what you say, I suspect the problem is with some contributed code hooking on the comment form and modifying it in a way that makes it fail submission. This can be caused by a number of causes: a jQuery that adds fields to the form without regenerating the form-id on the server, an added or cusomised field that changes the callback to submit the form, etc...
I cannot know it for sure, but here's what I would do if I were you, in order to check what's up with your installation:
Make sure you disinstalled (and not only disabled) the modules you tried and don't use anymore. Modules should never touch core tables, but who knows... It does not cost anything and it actually frees some of your DB.
Try disabling all contrib modules and see if you can comment that way. If this is the case, activate the contrib modules one at a time until you find out which one is the culprit. Chances are you will already find a patch/workaround in the issue queue for that module on http://drupal.org. If you don't find a fix, I would investigate (xdebug or manual tracking) the code, and I would pay special attention to all implementations of hook_form_alter() and hook_form_FORM_ID_alter().
If even disabling all contrib modules doesn't help (which I would be very astonished of), try updating the core with a fresh installation if you consider as a possibility that your cat walked on the keyboard while you had a core file opened, or you live with Gordon Brown's family.
Failing that, the only alternatives coming to my mind are much more esoteric, such DB failure, a greasemonkey script on your browser interfering with commenting and similar unlikely possibilities.
HTH!