There are several things that come to mind, as I too have experienced similar on occasion.

You already looked at the ADD-INS which is the first thing to do. Since it is no longer listed there amongst the other addins ... sounds like maybe there is a setting / or entry somewhere in your system still pointing to the software ?

Do you have any software that reviews the Windows Registry to remove outdated entries ? If not, for what it is worth, I use the free version of IOBit software. They produce several different pieces of software that perform various functions. One is the Registry cleaner.

What about a Software Uninstaller ? You indicated you've already uninstalled the softwar package ... was it using the software manufacturer's built-in uninstaller ? Again, IOBit has an excellent free version. The problem though, if you were not using IOBit at the time of installation of the problem software, IOBit uninstaller may not be able to locate the software "leftovers".

My last gasp approach is to uninstall EXCEL (mine comes with the Office Pkg so I uninstall the entire thing) .. then re-install. That method has never failed to clean up persistent issues that simply won't go away. It's drastic ... but it works here.

I too run Excel 2007. Been thinking about upgrading due to lack of support from MS. I've downloaded and saved all of the last upgrades to 2007 for use in the future just in case I need to re-install everything. Sooner or later, even the upgrades will no longer be available.

My 2 cents.

Cheers.