Has anyone had an issue with Excel add-in coming back in after it was disabled or heard complaints about Excel taking a long time to open?

That is defined by LoadBehavior value (stored in the registry) by default it is set as 3 - load at startup.
It could be there in the user’s registry so they might be able to change it to 1 which is load - do not start or even 0 - unloaded.
have you used the Spreadsheet tool in the app heavily? It is an awesome tool and I know it is fairly new but it is a slower, clunkier, and has fewer features than regular Excel. I hesitate to push users to it because of this. Just my .02