Give these steps a try: Go into your time and date settings on your device, turn off the automatic time and date settings, then restart your device, and turn the automatic time and date settings back on. Please let us know if that changes the order of your messages.
I realize you have performed these steps before, but let's give them one more try.
Please go to your Settings> Applications to clear the cache of the Messages app. Clear the App Cache and Data on Your Phone
Then test your phone while in Safe Mode to see if you still have the issue with the text. Safe Mode will disable your 3rd party apps, But you will still be able to make and receive calls and text. Keep the phone in Safe Mode until you've had the opportunity to fully test the function. Power On Your Phone in Safe Mode
Let me know if the issue continues.
Ok, I believe this may have fixed the issue. The act of switching over to the carrier determining the time zone and restarting the phone may have fixed the issue. If any issues continue, I will repost if need be. Thank you!