In my opinion, this is a very serious bug and I don't understand why it has not been fixed yet. I've had this happen to me three times in the past couple of months and I've written posts here and on the technical discussion forum before.
I do not believe that I've heard of this being reported and there is nothing like it described
on the issue tracker.
I completely believe that you may fail to broadcast initially if, for example, you transmit immediately after starting. But if your node is synced up you should be rebroadcasting with a random delay after every block that lacks your transaction. I'm quite sure that this has worked in the past but there is always a possibility of a bug.
Are you sure that you were not ending up with a double spent transaction in your wallet?— say from running the same private keys in another wallet? I ask this because it would have behavior like you described and be cured by doing what you describe, but is currently the expected behavior. In a double-spend case it will also still wedge some of your coins but it will be hopeless: the wallet will rebroadcast the conflicted transaction forever and the only way to recover any non-double-spent inputs will be to blow away the transaction just as you did. (This can be more easily done by backing up the wallet and then starting with salvage wallet). But outside of a double spend this would be very unexpected.
Do you have a debug.log from a wallet running in this state?
If you get wedged again a debug log from the wallet running with debug=1 and logtimestamps=1 in the bitcoin.conf would be very useful. If it is merely stuck needing a rebroadcast the transaction can be extracted by typing getrawtransaction
in the debug console and then manually broadcast.