COM registration requires write access to the HKEY_LOCAL_MACHINE
part of the registry.
Under UAC, write access to the HKEY_LOCAL_MACHINE
requires an elevated administrator.
The easiest way to get an elevated process is to create it with a manifest that specifies 'requireAdministrator' access. - Look under the Project Properties -> Configuration Properties->Linker->Manifest File->UAC Execution Level to set the correct setting.
This means you will probably want to split your EXE into two parts. The 'normal' asInvoker part, and, when self registration is detected as a requirement, an elevated InstallMyself part. When the non elevated part detects a first-run type condition, it needs to use ShellExecute(Ex) to execute the FirstInstall.exe part - using CreateProcess or some other API will simply fail with a insufficient privilege error. ShellExecute will present the UAC prompt.
It is possible to use Application Isolation to load COM dll's without any registration step at all.
Is is unfortunate that the cause cannot be determined. However, if you are interested in doing further research, a tool that will help a lot would be Process Monitor from SysInternals. Process Monitor can log all the File, Registry and other access for a process, including all success and fail codes making it a lot easier to debug problems like this without having to resort to deeper means of reverse engineering.