What do I need to do to deploy a .NET COM Interop DLL for MS Office?

I have written a .NET DLL (in C#)  that handles some advanced mathematics; some of the classes/methods are exposed to COM. To make use of this I have developed an Excel Add-In that instantiates the classes and calls the methods.

This works perfectly on my development machine, so I set about creating an installer using NSIS in order to deploy and register the DLL and add-in. This too works successfully, but, and here's inlies the problem; only for other development machines i.e. those with VS2005 installed.

To test the theory I took a standard build company laptop, installed the DLL and XLA and tested the example excel docs. This generated run-time errors. I unistalled the DLL and XLA, installed VS2005 and reinstalled the DLL and XLA, on testing the new setup there are no run-time errors and the process' complete successfully.

I suspect that this has something to do with the primary interop references used by the .NET DLL (Microsoft.Office.Interop.Excel), and whilst I have found plenty of reference to this sort of problem on the web, none provide any answers. If anyone can suggest what might be causing this it would be much appreciated.

FYI My .NET assembly (DLL) is not strong-named, as it has dependent assemblies which are also not strong-named, and it does not need to be installed in the GAC. The installer registers the DLL using regasm with the /codebase and /tlb flags, this creates the correct entries in the registry root HKCR.