I mean, if I'm a PC vendor, should I have the right to preinstall Red Hat, remove a bunch of stuff and generally mess up the system, and still advertise my PCs as having Red Hat preinstalled?

I won't belabour my first point except to mention how ridiculous it is to describe "custom configuration" as "genarlly mess up the system."

My real issue with this is that the legitimate point you actually have is with the vendor then making claims as to what is installed. Microsoft in fact got into this trouble by shipping a JVM that didn't actually conform to Sun's Java standards, and they were told they couldn't then claim it was Java(tm).

Assuming you are right about vendors not being allowed to "mess up" the system and still make claims as to what is inside, all that would be required is accurate disclosure that the software installed has been configured/modified from it's default configuration. At most this would allow Microsoft to disclaim responsibility for tech support, but they generally do that anyway if you buy a system with Windows pre-installed.