We'd heard that the iPhone 1.1.3 update was causing major problems with SMS message order, but a new support doc up on Apple's site points to a relatively simple fix: turning on automatic date / time updates. Apparently the problem is caused when the internal clock doesn't match up to the carrier clock -- which seems like it'll be a continuing annoyance for frequent travelers, so hopefully a better solution is in the works.

http://www.engadget.com/2008/01/29/a...ering-problem/