What might cause the Bitcoin client to take a long time to see a new, unconfirmed transaction? 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.