In my experience, those do not show immediately on the chain (the app's status shows "this transaction has not been sent yet").
Building up chains of unconfirmed transactions is not in itself a problem (they can/should all confirm together).
However, if the app says "this transaction has not been sent yet" then this means one of four things:
1) Your internet connection wasn't working.
2) You have set a "trusted peer" (this confuses the ui a bit - known bug, issue in bitcoinj really).
3) There's an unknown bug that was causing the transaction to not be sent.
4) There's an unknown bug that causes the transactions to be sent, but the app doesn't recognise it.
I have a vague feeling I might know what (3) or (4) could be. If you send a transaction and you don't have internet access at the time (or it's flaky etc) then the transaction won't be broadcast. You won't be allowed to extend an unbroadcast transaction chain (you won't be allowed to spend the change). However if you then regain internet access, bitcoinj will announce the transactions to all newly connected peers at once and thus won't get a chance to see them propagate.
Andreas, does that sound about right? If so, it should not be hard to reproduce this and verify the hypothesis. If correct then it should be an easy fix. It means changing how pending transactions are announced to new peers such that rather than announcing them as soon as a peer is connected, all pending transactions in the wallet are broadcast along the standard codepath (using PeerGroup.broadcastTransaction), to allow observation of the propagation.
It'd be even better of course if the P2P protocol informed you if a tx was rejected. Then we could simply this "seen by X peers" tracking code significantly. I might submit a pullreq to do that at some point.