After much fruitful discussion and evolution, this proposal is now a series of "Bitcoin Improvement Proposals" -- see BIP 11, 12 and 13: https://en.bitcoin.it/wiki/Bitcoin_Improvement_Proposals
Sincere thanks to everybody who contributed improvements, ideas and code.
Groffer's above proposal has the advantage of being much more general than the ad-hoc constructions specified here.
Gavin says "optimizing for size is worthwhile, even if that means more work for implementors"
More work for implementors means delay in implementation and more volume for bugs as optimised cases are added in future.
Gavin says "Users will pay for extra bytes in transactions via transaction fees over and over again".
Then change the fees to reflect the real costs and incentives. Transactions and the block chain are already take significantly more bytes than necessary but it's not considered a problem. Currently the concern is the number of verifications. In this case change the fees to reflect the worst-case number of verifications to spend the transaction.