Thank you! The TMM overview document was very interesting and highly relevant to this discussion: http://www.microsoft.com/whdc/system/platform/mobilepc/tmm.mspx
I had never heard of TMM, and have never used Vista, but they have basically captured exactly what I was trying to express in the hypothetical use cases - they even use the phrase "it just works!" :-)
To summarise: they say it works fine with DVI and that for DVI that it works without polling using interruptible HPD. For VGA, they say there are known problems with autodetection, but that they're using periodic DCC polling using the I2C bus, and that it only works for analog displays with EDID support, and that they use non-destructive polling unless requested to detect something by the user, and that non-destructive polling does not cause any visual artefacts or flashing, and that the specific implementation for polling is up to the hardware vendor (maybe it's part of the Windows driver supplied by the hardware vendor?). For VGA polling, it happens once per second or less. There is no polling of TV outputs, and TV-out is not really covered very much, and is doesn't sound like it gets any of the benefits of auto-detection. Hardware must work with TMM in order to get the top level of Vista certification.
Bottom line: It is possible to do this, especially for hardware that already works with this TMM thing. However there would almost certainly be some older or cheaper display adapters that do not work (if there wasn't, Microsoft would have no need for a certification requirement), so there would have to be a white-list of known supported cards, or in X the driver would have to say if the hardware was capable of this. And frankly, that's fine - if the hardware can't do it in a non-obtrusive way, then the hardware can't do it, and that's just the way it is. But, it is definitely do-able, for at least some hardware, and TMM serves as a "proof-by-existence" of this.