This really does sound like something you won't solve without Salesforce Support as we don't have any control over concatenation apart from this checkbox and can't set an order in which the parts would be delivered.
Create a support case and follow the guidelines (from this article):
Minimum Information Needed to Investigate
It's very likely the support agent that gets the case will try to ask for this and refuse to investigate the issue until you provide this data.
We can only speculate what's going on, but one likely cause would be that the integration between Marketing Cloud and the local operator company that is performing the SMS sends is not working properly. Only support agent could work with this other company and use your examples to identify any issues.