Random Bitcoin address generation From https://en.bitcoin.it/wiki/Address:


  A Bitcoin address, or simply address, is an identifier of 27-34 alphanumeric characters, beginning with the number 1 or 3, that represents a possible destination for a Bitcoin payment.


Is any random address I create following the above rules going to be an address I can sucesfully send Bitcoin to?

For example if I randomly generate these addresses:


1AAAAAAAAAAAAAAAAAAAAAAAAAA
3111111111111111111111111111111111
2FWIOHFEWNFEOWEFHO34234242244EFDE


Are these all valid addresses I can always send Bitcoin payments to?  Or do they have to already 'exist' in some capacity?
Addresses are randomly generated starting from a private key. The private key is the only truly random value in a whole chain of interesting values. These values are then mathematically derived from the private key. On the other end of the chain of values is the address.

Now if you could simply pick an address and recover the private key that, when passing it through the address derivation mechanism, gives you that address we would be in a lot of trouble. People could simply listen to transactions on the network, extract the receiving address, reconstruct the private key and spend the funds, even if they were not the intended recipient. So at this point it should be clear that simply picking an address and go ahead from there is not possible, in other words some of the functions in the chain are non-reversible.

So starting from the private key, we construct a public key. Already this first step is non-reversible, otherwise public-key cryptosystems would stop working. It should be computationally unfeasible to recover the private key from the public key. Bitcoin further goes ahead and hashes the public key twice. This step is non-reversible as well.

The first character of the address depends on the address version and may not be freely chosen. Then there is the matter of the Base58 encoding, which unlike the other mechanisms is reversible.

Finally the last few characters in the address are a checksum which is again calculated as a double hash of the already hashed public key. So for these last characters there is simply no way of "choosing" them so that the address looks a certain way.

So to answer your question: no, you cannot simply pick an Address that looks nice and use it as yours. That's also the reason why tools like vanitygen exist: they simply pick a random private key, transform it until they get an address and then check whether it has the desired features, e.g., your name in it. The more restrictive you are with what you want your address to look like, the harder it gets to find one that does. This difficulty increases exponentially, hence the term computationally unfeasible above.