We found the cause, but not the reason.
The cause was we have, via Group Policy, defined our "my Documents" to live on the network - a mapped drive u:\
Users with the default (c:\documents and settings\username\) worked fine, as soon as we made the change to the network this broke (BTW our Local Admin accounts had it set to the local drive, which is why it appeared to work when logged in as an admin)
Esri(UK) failed to recreate the problem, so we assumed that something isn't quite right with our GPOs.
However, by setting the registry to look for shared AddIns (which was my ultimate goal anyway - just let the users use add-ins from a central location) it all worked.