You cannot send coins to an address does not exist. For example you cannot send coins to an address that doesn't start with 1. The client will tell you this after you attempt to send the coins.
If you send coins the first step is usualy verifiy that the address is a valid bitcoin address. If it's valid then the online computer will send the coins off to that address, whether it's been used before or not. It doesn't have to be on the network for it to be a valid address. There are 2^256 address, and we haven't even made speckle of those addresses yet. Those coins will sit at that address. The address doesn't have to be electronic, it can be paper, steel, whatever. The coins are on the address (which is thus in the network), not the device or object that holds the coins.
Hope that clears it up.
That's what I meant. As long as the address has a valid format, the coins will be sent, even if that address has no corresponding private key stored anywhere.