I found a fix for my system (Vista Ultimate 64-bit). The Start menu's recent programs are working again.
Using regedit, delete this key...
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\UserAssist
Windows will rebuild it on restart. To play it safe, I exported the current key, but it wasn't necessary.