I have found a pattern for this problem.
1. Doesnt’t matter how many comments you have;
2. Doesnt’t matter what theme you have installed;
3. Comments show up in order if you disable threaded comments;
By default, most of the themes with threaded comments support have that “Reply” button removed when a comment reaches 3/4/5 (depending of your options) levels of comments. That’s great but how about the edit_comments.php section from the admin area? The reply link is still there even if you reach your selected number of levels.
So, if you reply to a comment that has reached the max numbers of comments, from the admin area, this comment will show up in the bottom of the page and messes everything up.
I’ve made a test post to see what i mean, i can easily replicate the problem.
Very sorry for my bad english, i hope you guys can understand what i have just said:)