One remark I would like to interject:

As much as possible of all this work (identifying "best" drivers,
figuring out whether some hardware was "added" or "deleted" or
perhaps just "moved" or whatever) as possible, should be done in
user mode.

The initial autoconfiguration has a bootstrap problem here, but
one the system is up, auto-*re*-configuration should be something
that can be driven from user mode, with the assistance of kernel
level hooks (e.g., bus suspend+scan+resume calls).

This means LKM-searching can be arbitrarily complicated, without
making the kernel arbitrarily complicated. :-)

Chris