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.