I agree that Microsoft Active Setup is the correct solution in this case. The problem with the MSI self-healing idea is that the user isn't invoking that plug-in when launching Excel. They're invoking Excel, and therefore the MSI self-healing mechanism is only concerned with the health of the component keypaths that are in the Excel MSI.
Without seeing the Excel plug-in MSI package, I can't say for certain...but I am fairly sure that there are no valid MSI entry points being invoked when that plug-in is loaded. And that means no self-healing for the MSI package. It would be good to take a quick look at the MSI's tables (AppId, Class, Extension, MIME, ODBCDataSource, ProgId, Shortcut, TypeLib, Verb) to see if any valid entry points exist. If all of those tables are empty, abandon all hope for MSI self-healing.