I did yet another reinstall, this time uninstalling using the removal
tool that was intended for removing the Betas (hoping it would clean up
a bit more). In addition to that, I tried to remove virtually
everything that looked like configuration data somewhat related to
vsmsvr.exe, from the registry (HKLM and HKCU) and from the Application
Data folders (VSA\8.0). Unfortunately, after installing VS2005, the
problem occurred again.

"Just for fun" I removed vsmsvr.exe and vsmsvr.exe.config , hoping I
would trigger some kind of repair mechanism of VS. Funny thing, I can
now record a macro, enter the macro IDE and leave it again without
getting an exception, but of course I cannot play back any macros
(d'oh).

I then copied both files back to their original place, but the
exception is there again.

Just to give as much information as possible, there are two occasions
when I get an execption:

1. Record a (temporary) macro in Visual Studio, then try to play it
back -> Exception
2. Enter the macro IDE, edit some macro (maybe just change a comment)
and save it. Leave the macro IDE -> Exception

The exception is in vsmsvr.exe, "unknown software exception
(0x40000015) occurred in the application at location 0x7813461a."