Auto Publish in XP Mode stopped working

I am a big fan of the XP mode in Windows 7. A.o. it allows me to verify websites that I maintain in IE6, even side-by-side to IE8.

One nice feature is that you can have XP applications appear in the Start Menu of Windows 7, with “Auto Publish“. If Enabled in the XP Mode Settings, any shortcut you add to the All Users Start Menu in XP Mode, will appear in the Windows 7 Start Menu under Windows Virtual PC > Windows XP Mode Applications:

Yesterday however, I noticed that the shortcut for IE6 that I had there, no longer worked. I removed the shortcut in the Start Menu of All Users in XP Mode and added it again, but that did not help. In fact, anything I added to the All Users Start Menu no longer appeared in the Start Menu of Windows 7.
When I checked the Settings of XP Mode, Auto Publish was grayed out, with an obscure error message about not having the latest updates. After a lot of trouble-shooting, without avail, I finally uninstalled XP Mode (via Windows 7’s Control Panel > Programs and features) and reinstalled it. That brought back the Auto Publish feature:

I have no clue about what went wrong, but I have a working IE6 shortcut in my Windows 7 Start Menu again.