I can't say for sure why is that happening, but I have a hunch...
I bet you any money that your site went through few Joomla updates, and that at some point in time was on J! lower than 3.6.3.
You see, J!3.6.0 which was released on 2016-07-12, introduced a change in New Article Ordering. Until then, since a dawn of time, every new article when created, used to be assigned ordering 0, and all previous article's orders were increased by one, thus putting new article at top, as a first one. Thousands of Joomla admins relied on that fact with their category blog menu sorting settings, and everything was nice and dandy. You could set menu sorting as "By Order" and it would at the same time act as "Most Recent First", thus making admin's life much easier.
Then with PR #8576 Performance gain - new featured article (which on Apr 15 found it's way to RTC for J! 3.5.2, and was renamed to J! 3.6.0) they rightfully claimed it is performance bottleneck for categories with hundreds of articles, and thus changed Ordering for New Articles to Last! It was a nice improvement strictly performance-wise, but at the same time it introduced Backwards Compatibilty Break for thousands of existing sites, whose webmasters were crying foul left and right.
Then again with PR #11581 Revert "Performance gain - new featured article" and after heated discussion in Issue #11103 New articles are created with last possible "ordering" , PLT accepted mistake and Backwards Compatibility Break and Released J! 3.6.3, which returned to good-old New Article First Ordering. Not to mention that update was sitting on shelf for more than a month with no apparent reason, additionaly causing some webmasters to go bezerk.
Now, you see what I'm suggesting? If you have created a bunch of articles while being on version before J!3.6.0 they went to the top. Then later if you created articles while being on J!3.6.0 until J!3.6.3, they went to the bottom. Then finaly after J!3.6.3 update they again went to the top.
If that is not a Scenario for Great Conundrum, I don't know what is.
Now if that is true reason for your problems, I am in loss for words how to fix it. Haven't got a slightest clue, to be honest. I for one would love to know how to fix it on my sites. :-(