there is nothing you can do to prevent someone from using it more than once
Well, technically the network could prohibit it. E.g. Bytecoin (and its forks) prohibit a single public key from ever being spent from more than once. Zerocash will also require such a restriction.
You could hardfork Bitcoin with an additional transaction validity rule,
Such a change is merely a soft-forking change, it only restricts the set of valid behaviors.
But it would increase the demands on computer resources required to validate the blockchain considerably, because they'd have to keep track of all txouts rather than just unspent txouts.
Right, it requires an an unprunable data structure that will grow forever. However, you could make it lossy with most of the same privacy effect, e.g. you can't use an address used anywhere in the last 2016 blocks. This isn't an option in bytecoin, since it needs the non-reuse invariant to prevent double-spends.
I've considered this, mostly because it would shut down (existing) pools, and I think pools are bad because they can easily be used for attacks and the miners don't even necessarily know what they're hashing on.
hah well if this was your motivation then I guess you couldn't deploy that as a soft fork.
But you're wrong there wrt pools, it would be very easy for pools to switch to paying BIP32 chains or ECDH addresses— and they should, for privacy reasons. Eligius' prior operator (Luke) wanted to do this, but the new management is less interested in doing things which are of long-term benefit.
For a little while Eligius was generally deprioritizing recent-address-reusing payments in their block selection as a way to discourage reuse generally and to also give more fair access to the blockchain. I'm not sure if they're still doing that.
But the reasons why people want to use pools would still be there, and they would just create a new pool protocol that conformed to the rule using BIP16 addresses (which they ought to do anyway). Ultimately, it wouldn't shut down pools, although it would make them more private.
Or that.
The right way to get rid of pools is to do something that addresses the reasons (such as distributed pool software), rather than just firing the opening shot in something guaranteed to become an arms race.
Welp, P2Pool exists, and could use some more love and attention.