Guys, this is a big problem. Inconsistency with propagation of unconfirmed transactions makes payment timeout mechanisms, so popular with Bitcoin merchants, horribly unreliable... Think of 15 minute timeout, the payment processor gives you to see the transaction on the network.

Something needs to be done. I am not sure, raising the number of nodes wallets broadcast through, maybe.