Sorry if it's bad etiquette to answer my own question.
Recently I stumbled upon the information on DISABLEADVTSHORTCUTS property. I created an install with advertised shortcuts and set the DISABLEADVTSHORTCUTS property to 1 which produced non-advertised shortcuts. This bypasses ICE43 errors because an advertised shortcut can use a file as a keypath. Because DISABLEADVTSHORTCUTS has been set Windows Installer will replace these advertised shortcuts with regular shortcuts.
I set the Package Element's InstallScope attribute to "perMachine". This sets the ALLUSERS property to 1. The values of ProgramMenuFolder and DesktopFolder will then resolve to the All Users profile.
For folders created under ProgramMenuFolder there is a RemoveFolder and RegistryValue element. The examples I've seen (ex1, ex2) use HKCU as the root for the RegistryValue. I changed this root to HKMU which resolves to HKCU or HKLM depending on the value of ALLUSERS.
In short, with DISABLEADVTSHORTCUTS set to 1 your advertised shortcuts will not produce ICE errors, but will be converted to non-advertised shortcuts when installed. A RegistryValue with root HKMU is fine for a KeyPath as long as it's not keypath for a non-advertised shortcut.
<?xml version="1.0" encoding="utf-8"?>
<!-- This example is based on SampleFirst by Gábor DEÁK JAHN, Tramontána:
http://www.tramontana.co.hu/wix/lesson1.php#1.3
Original SampleFirst:
http://www.tramontana.co.hu/wix/download.php?file=samples/samplefirst.zip&type=application/zip -->
<Wix xmlns="http://schemas.microsoft.com/wix/2006/wi">
<Product Name="Foobar 1.0" Id="YOURGUID-21F1-4026-ABD2-7CC7F8CE4D18" UpgradeCode="YOURGUID-AFA4-46C6-94AA-EEE3D104F903" Language="1033" Codepage="1252" Version="1.0.0" Manufacturer="Acme Ltd.">
<Package Id="*" Keywords="Installer" Description="Acme's Foobar 1.0 Installer" Comments="Foobar is a registered trademark of Acme Ltd." Manufacturer="Acme Ltd." InstallerVersion="100" Languages="1033" Compressed="yes" SummaryCodepage="1252" InstallScope="perMachine" />
<Media Id="1" Cabinet="Sample.cab" EmbedCab="yes" DiskPrompt="CD-ROM #1" />
<Property Id="DiskPrompt" Value="Acme's Foobar 1.0 Installation [1]" />
<Property Id="DISABLEADVTSHORTCUTS" Value="1" />
<Directory Id="TARGETDIR" Name="SourceDir">
<Directory Id="ProgramFilesFolder" Name="PFiles">
<Directory Id="Acme" Name="Acme">
<Directory Id="INSTALLDIR" Name="Foobar 1.0">
<Component Id="MainExecutable" Guid="YOURGUID-3E4F-47A2-86F1-F3162E9C4798">
<File Id="FoobarEXE" Name="FoobarAppl10.exe" DiskId="1" Source="FoobarAppl10.exe" KeyPath="yes">
<Shortcut Id="startmenuFoobar10" Directory="ProgramMenuDir" Name="Foobar 1.0" WorkingDirectory="INSTALLDIR" Icon="Foobar10.exe" IconIndex="0" Advertise="yes" />
<Shortcut Id="desktopFoobar10" Directory="DesktopFolder" Name="Foobar 1.0" WorkingDirectory="INSTALLDIR" Icon="Foobar10.exe" IconIndex="0" Advertise="yes" />
</File>
</Component>
<Component Id="HelperLibrary" Guid="YOURGUID-C7DA-4C02-A2F0-A6E089FC0CF3">
<File Id="HelperDLL" Name="Helper.dll" DiskId="1" Source="Helper.dll" KeyPath="yes" />
</Component>
<Component Id="Manual" Guid="YOURGUID-FF92-4BF4-A322-819A3B2265A0">
<File Id="Manual" Name="Manual.pdf" DiskId="1" Source="Manual.pdf" KeyPath="yes">
<Shortcut Id="startmenuManual" Directory="ProgramMenuDir" Name="Instruction Manual" Advertise="yes" />
</File>
</Component>
</Directory>
</Directory>
</Directory>
<Directory Id="ProgramMenuFolder" Name="Programs">
<Directory Id="ProgramMenuDir" Name="Foobar 1.0">
<Component Id="ProgramMenuDir" Guid="YOURGUID-D1C2-4D76-BA46-C6FA79862E77">
<RemoveFolder Id="ProgramMenuDir" On="uninstall" />
<RegistryValue Root="HKMU" Key="Software\[Manufacturer]\[ProductName]" Type="string" Value="" KeyPath="yes" />
</Component>
</Directory>
</Directory>
<Directory Id="DesktopFolder" Name="Desktop" />
</Directory>
<Feature Id="Complete" Level="1">
<ComponentRef Id="MainExecutable" />
<ComponentRef Id="HelperLibrary" />
<ComponentRef Id="Manual" />
<ComponentRef Id="ProgramMenuDir" />
</Feature>
<Icon Id="Foobar10.exe" SourceFile="FoobarAppl10.exe" />
</Product>
</Wix>