> I think it would be worthwhile thinking about what an acceptable solution would look like.
Make it easy to temporarily allow anything to both boot and add new keys to the trusted store. For instance, the same key combination you already have to use to boot from the install DVD could do this. Then it is a simple matter of changing the OS installer to add its key to the trusted store (either a fixed one or a new one generated on the fly). This keeps the install of a new operating system almost as easy as it currently is (it would only break Windows-based OS installers), while completely blocking software-only malware (the only way to bypass would be with hardware pretending to be an USB keyboard).
It could also have a disable switch on the firmware setup screen, much like the on every system I have seen so far with a TPM (but that is much less discoverable for users who just want to install from a DVD).
> Now Linux is big enough that it will merely be worrysome.
Linux might be big enough, but Linux hardware OEMs are not that big AFAIK. With the exception of Asus netbooks, every Linux desktop/laptop computer I have personally seen either originally had Windows installed by the OEM or was built from components (including a blank HD). And when the big OEMs have a Linux option, it is as far as I have seen only on lower-end hardware (as if the only reason to use Linux were lower prices!), or on servers.
That is, most people end up buying a computer with Windows preinstalled, even if they end up using Linux. If this makes it impossible to install Linux on these computers, it would for instance make it much harder for new people to try Linux.