important: this answer refers to the public address, not private key, see comments.
Every hex string is a valid Ethereum address.
Currently there are no address checksums implemented, so all the 0x<40 hex digits here>
are valid. We are considering adding basic ICAP in Geth 1.4.1 or Geth 1.5 to allow inserting additional information into an address that would prevent mistyping them, but until then as long as it's 40 hex characters, it's valid.