It's actually not that weird at all. COM extraction / harvesting is a tricky business. Given enough COM components and you'll find that frequently it doesn't go well.
You already have half the problem solved. The fact that regsvr32 fixes the problem tells you that you are close and not missing other dependencies and what not.
What you want to do is get a clean machine ( VM's are great for this stuff ) in the state where you are installed but only one is registered. Use a tool that can scan and capture the registry (InstallWatch is a decent one) before and after running regsvr32. Then compare the snapshot to see what changed.
You'll have to filter out some noise from other processes on the machine but with a little experience it should be obvious what changed. Work this into your wxs source, rebuild and retest ( again VM's are great ).