In case anyone cares and finds this (as per
http://xkcd.com/979/) I'll include what I have found.
The order of the transactions does not seem to matter. However, you need agreement between what you send for blockchain.address.get_history and the order used for making the hash in blockchain.address.subscribe or the client will reject it.
The client is taking the list from the history message (in the order that they appear) and doing the hash and making sure that matches with the hash given by the address subscription.
In both the history and the hash, an unconfirmed transaction should be listed with a height of 0. This was getting me because I happened to be using the string 'null' instread of zero for the hash and then the client was rejecting my address history.
So I am ordering by transaction ID and that seems to work well.
This of course means there is a race condition between when you report a new hash and when the client asks for the history. If there is more action on that address between those two, the client will reject the history and not try again. I think it stayed in state synchronizing which would probably work. The new address hash should come in and then the client should ask for the new history and get it again, hopefully matching this time. So this is actually probably a self-correcting problem assuming your server isn't pants-on-head.