My Comments Do not Publish

Hi folks
I’d appreciate it if anyone can help me out with this comment issue on my blog myparnasa.com
The Problem
A few months ago I started getting an error on my blog that most comments do not go through.
The reader posts the comment, I get an email notifying me that it was posted, but when I click to approve it, I get an error message in my dashboard:
Oops, no comment with this ID.
This is now happen with most comments on my site and it’s really annoying. Sometimes I repost the comments manually from a different browser. Usually it goes through then without an error (but not always).
Also I noticed that if the person is a repeat commenter, who does not require my approval, the comment usually goes through without a hitch.
My attempts to resolve it
From what I read, this problem could either come from the database or the code (e.g. a theme or plugin conflict). I checked on the comments in my latest post in MyPHPAdmin and I can see that these comments do not exist in the database at all.
So I assume that this is not a theme or plugin conflict, but rather an issue with the database.
So what do I do next?
Thanks!