The Bitcoin address is just some chain of hashes (and a checksum) applied to the public key. To prove that the address IS actually output from the hash functions [and not spam], simply provide the public key along with it. Of course, you might say that is way too much data for the blockchain to handle. So you only limit the requirement of providing the public key to "suspicious" transactions. What constitutes a suspicious transaction could be a matter of debate, but I imagine it could be done, and it would avoid the problem of a Bitcoin's value depending on its ancestry.
