I've noticed that sometimes, when I send Bitcoins from one client to another, the recipient client might not see the transaction, sometimes until it already has one or more confirmations. Both clients are connected to 30-40 nodes.
Is one of the clients disconnected when you send payment with the other? This often happens to me when I send a transaction to the other OS on a dual-boot system, meaning the receiving client is down when the transaction is broadcast.
I'm guessing this happens because all nodes the client connects to when he comes online have already broadcast the transaction, so they won't send it again to him. He'll only get it as part of a block when it is found.
If the transaction is "spam-like" other nodes won't relay it. This is to help protect the Bitcoin network from too many low priority transactions.
Was the transaction for a tiny amount? (e.g., under 0.01 BTC?) and no fee paid? If so, that's kind of "spam-like". I don't know the exact algorithm, but both of those are factors.