Can we design the protocol, so that an address can only be used once as an output in a transaction? Most users reuse their addresses for deposits (ie. they receive money more than once on a given address).
Can the protocol be designed in such a way that an address can be used only once as an output in a transaction?
I guess there would need to be a way of quickly looking up if an address was already "used-up".
Also there would need to be a way to somehow to get "next address". For eg if an address is used for dividends and it can be used only once, the dividend payer should be able to automatically get a new address without the owner's (payee's) repeated input. (a one time set up of this, would be ok)
The point of this is to enhance privacy.

These are just thoughts, comments welcome.
Alice gets her computer hacked by Mallory, and she steals her wallet. Fortunately, Alice had encrypted it with a strong passphrase. Alice wants to sue Mallory for breaking into her computer, so she gets a lawyer, Bob.


Alice's address, 10BTC --> Bob's address


Unfortunately for Alice, Mallory controls a node on the Bitcoin network, not too far from Alice, that quickly sees the transaction is from Alice (she has all her addresses), and instead relays, to hundreds of nodes at once, the transaction:


Mallory's address, 1000 satoshis --> Bob's address


Which is incompatible with Alice's honest transaction.

Now, three things happen:

1) Alice tries to send the bitcoins to a different address given by Bob

2) Alice's nodes see her transaction as a double spend, and refuse to relay any transaction spending that coin to a different address

3) Mallory's transaction eventually gets mined. Back to trying to spend the coins to Bob.

Mallory can do other mischievous things with her position, such as allowing Alice to spend her bitcoin at a church fundraiser but not an abortion clinic (assuming she knows the address of both).

The main way people lose their privacy in bitcoin today is through heuristic analysis of the blockchain, not address reuse. Introducing a new network rule to protect users against their own stupidity will not significantly improve privacy (most wallets don't reuse addresses by default anyway), and opens up users to some interesting attacks.