If deleting and redownloading the block chain does make a difference, there is something seriously wrong, and we have a bug to fix.
That's what I mean. Once a transaction gets stuck at 0 confirmations (in the block chain, but not detected by the client), deleting the block database will help, but -rescan won't.
I haven't had this happen to me, but I've read several cases of it on the forum.