What would happen if the Wallet address did not exist at all? (incomplete copy of address, typo etc)?
It would not be a valid address and the client (i suppose all clients...) would not let you make the transaction. I suppose it apply to deepbit too.
Note that the "an address not exist" thing only apply to a mistyped address. If you insert a valid address wich does not exist, you can happily send the bitcoins to it, in a black hole