First of all, I am not quite sure if this is exactly Mollom problem.
This strange behaviour appears randomly for both anonymous AND privileged users, for whom Mollom moderation should not be working. It's pretty rare.
While previewing comment one can see check box "Published" is checked, though after submitting comment still becomes marked as "Unpublished" - it resides in "Approval queue" and can be successfully published only from there. For anonymous posters, obviously, no check box is visible, but "Unpublished" anonymous comments keeps appearing time to time.
Mollom contend moderation settings is set to "Block all form submissions".
I could try to disable Mollom for a while to check if this could be the problem, but that would mean lots and lots of spam per day for us (Mollom does grate job!). So firstly I would like to use some "passive" debugging, with your help. Currently I am suspecting only Mollom (have not asked question in Drupal Core yet).