After all these weeks creating installers and uninstallers for add-ins, either for all users or for the current user, either using InnoSetup or MSI (through WiX), I have found quite a few issues. This is one of them:
PRB: Uninstaller does not remove commands of add-in if uninstalled from another user account
http://www.mztools.com/articles/2011/MZ2011021.aspx
This issue affects these two articles:
HOWTO: Create a setup for a Visual Studio add-in for all users (requiring admin rights) using Inno Setup
http://www.mztools.com/articles/2008/MZ2008010.aspx
HOWTO: Create a setup for a Visual Studio add-in for all users (requiring admin rights) using Windows Installer XML (WiX)
http://www.mztools.com/articles/2011/MZ2011019.aspx