A tx will go from your client (which should reject an invalid tx to start with) to a node (which will verify and reject an invalid tx) to many other nodes (which will all verify and reject an invalid tx) to the node that's publishing the next block (which will verify and reject an invalid tx). I guess a broken client could think a tx is valid when it's not and not let you re-spend it, but it'll be rejected pretty much immediately after that.
Technically there is no such thing as a nonexistent address. There are used and unused addresses -- an unused address is just an address with no history, but there's no way to tell if anyone has the private keys for it or not. I guess it's possible accidentally typo an address that somehow passes checksum (let's pretend that people actually type in addresses... nobody does that, copy/paste or QR code) but it's very very unlikely.
Technically there is no such thing as a nonexistent address. There are used and unused addresses -- an unused address is just an address with no history, but there's no way to tell if anyone has the private keys for it or not. I guess it's possible accidentally typo an address that somehow passes checksum (let's pretend that people actually type in addresses... nobody does that, copy/paste or QR code) but it's very very unlikely.
For the checksum tech details: https://en.bitcoin.it/wiki/Base58Check_encoding#Creating_a_B...