Actually, I did a 2-level testing.
First, i tested the "normal" client to check if it adds fees. Then i did an identical transaction with identical sum of money.
And guess what. The mainline client ALWAYS (state as of december 2011) wants a fee when you resend money that are younger than 30 minutes.
My client does not. And the transaction produced by my client got confirmed easily (up to 2 hours).
Ah.
What you're having happen there is that when you send your transaction is dropped by the network lacking the required fees because it looks like a DOS attack (fast turnaround), but after every block that doesn't contain your transaction the client tries retransmitting it (with a random delay). After two hours or so, the input coins have matured enough that they no longer require a fee. After that when your client resends then it goes through.
If you'd just waited the same time it would have sent without a fee in mainline. From a usability perspective, when the times are reasonably short, it might be better to wait like that... but if you shut down right after sending the transaction will be stuck until you start back up and wait an hour or so, and a lot of people do that.
I've had transaction queuing on my feature wishlist for a while (mostly for the purpose of automatically grouping transactions into a sendmany). Perhaps that would be a good way to address this.
FWIW, you can do this testing with Testnet too. So you can do a bunch without having to move around a bunch of real bitcoin.
There is a "cautionary" big, red warning in the first post, shouldn't that be enough ?
I don't know about you, but I usually skip to the end of long threads and don't bother reading much of the start.