A new software update for OS X today finally fixes the Messages bug. According to Apple, the update includes "A fix for an issue that may cause iMessages to display out of order in Messages."
This won't completely solve all the problems with Apple's Messages app, but hopefully it will at least take strides to make the app actually useable.
You can get the update through the App Store on your Mac, detailed info on the update is here.
