When BIP-16 was adopted, there was a sort of informal vote. Miners were asked to embed their vote in the coinbase transactions of blocks they mined and to switch to the new rules once a majority supported it:
On February 1, 2012, the block-chain will be examined to determine the number of blocks supporting pay-to-script-hash for the previous 7 days. If 550 or more contain "/P2SH/" in their coinbase, then all blocks with timestamps after 15 Feb 2012, 00:00:00 GMT shall have their pay-to-script-hash transactions fully validated. Approximately 1,000 blocks are created in a week; 550 should, therefore, be approximately 55% of the network supporting the new feature.
BIP 0016Users / owners / merchants didn't have a direct say. Indirectly they did get to vote with their feet and their transaction fees of course, but in order to avoid accidents it's good to have a mechanism that ensures you don't end up on the minority branch of a fork accidentally, while still influencing the outcome. I thought it might be useful to have a way for people who own or spend bitcoin to have a direct vote.
I'm thinking of something like embedding a vote (the hash of "I vote for/against BIP-XXX", perhaps with a hash of the BIP itself included in the string) in transactions using OP_RETURN. There are complications with this, and it probably not a good proposal as is, but I'd like to explore if we can think of improvements that would turn it into one.
Instead of requiring a majority (or supermajority) of coinbase-based votes in the last N blocks, you could require a double majority, i.e. a majority of coinbase-based votes as well as a majority of ordinary transaction-based votes.
To deal with ballot-stuffing, you could add up votes from the UTXO set at a pre-specified date, weighted by amount of BTC, perhaps limited to outputs belonging to transactions that were entered within the three months immediately preceding the cut-off date.
Complications include the hassle of doing this with coins in cold storage, privacy concerns, censorship concerns.