In bitcoind, an unconfirmed transaction may be lost if bitcoind restarts.
Unconfirmed transactions from other bitcoinds are stored in a memory pool so are lost when bitcoind stops.
Or, if for some reason the 0-confirm transaction didn't make it to the bitcoind (networks aren't perfect) it wont know about it (though rare)
This also means that if bitcoind wasn't running when the transaction was sent out, it won't know about it until either it ends up in a block, or some other 0-confirm transaction requires it and bitcoind requests it from another bitcoind.
i.e. it will eventually get the transaction back again since probably every other bitcoind still has it and eventually a block will include it.
But bitcoind may not find out about it until it lands in a block (which can be more than an hour on some rare occasions - or longer if some pools are ignoring processing the transaction)
My bitcoind runs 24/7, and has 4 specific other nodes that I run, which it connects to... This wallet is only used for Satoshidice, so no other TX's (aside from the one I funded the wallet with) exist.
Neither a rescan, nor a re-download of the blockchain resolved the issue.
I'm currently rebuilding the wallet by exporting all the private keys from it and re-importing them 1-by-1 into a new wallet... it will take a few days to run, since there are ~2100 private keys and it averages 45 seconds per key to import. I'll let you know how it works out.