I had a problem to register new addins in Visual Studio .NET 2003 that I exposed there : Refactoring my publishing tool. When I was starting Visual Studio .NET 2003 I got this dialog:

Now it is over. If you are facing the same issue here is how I solved it:

I installed the extensibility.dll in the CAG manually:

gacutil /i “C:\Program Files\Microsoft Visual Studio .NET 2003\Common7\IDE\PublicAssemblies\extensibility.dll”

Then reinstall or repair the addin installation with its setup. Thats it.