The methods described here doesn't work on my system. I have created a VBScript that does the job:
pin_explorer.vbsCODE
Set Shell = WScript.CreateObject("Shell.Application")
Set FSO = WScript.CreateObject("Scripting.FileSystemObject")
ssfPROGRAMS = 2
ssfCOMMONPROGRAMS = 23
ssfSTARTUP = 7
Select Case GetLocale()
Case 1033 strPinVerb = "P&in to Start Menu"
Case 1043 strPinVerb = "Aan het menu S&tart vastmaken"
End Select
' Pin Corel Paint Shop Pro shortcut to Start menu
Set objFolder = Shell.Namespace(ssfCOMMONPROGRAMS)
Set objFolderItem = objFolder.ParseName("Corel Paint Shop Pro X.lnk")
objFolderItem.InvokeVerb(strPinVerb)
' Pin FileZilla shortcut to Start menu
Set objFolder = Shell.Namespace(ssfCOMMONPROGRAMS)
Set objFolderItem = objFolder.ParseName("FileZilla.lnk")
objFolderItem.InvokeVerb(strPinVerb)
' Pin Nero Express shortcut to Start menu
Set objNeroFolderItem = Shell.Namespace(ssfCOMMONPROGRAMS).ParseName("Nero")
Set objNeroFolder = Shell.Namespace(objNeroFolderItem.Path)
Set objShortcutFolderItem = objNeroFolder.ParseName("Nero Express.lnk")
objShortcutFolderItem.InvokeVerb(strPinVerb)
' Pin Notepad++ shortcut to Start menu
Set objFolder = Shell.Namespace(ssfCOMMONPROGRAMS)
Set objFolderItem = objFolder.ParseName("Notepad++.lnk")
objFolderItem.InvokeVerb(strPinVerb)
' Pin OpenOffice.org Writer shortcut to Start menu
Set objOpenOfficeFolderItem = Shell.Namespace(ssfCOMMONPROGRAMS).ParseName("OpenOffice.org 2.4")
Set objOpenOfficeFolder = Shell.Namespace(objOpenOfficeFolderItem.Path)
Set objShortcutFolderItem = objOpenOfficeFolder.ParseName("OpenOffice.org Writer.lnk")
objShortcutFolderItem.InvokeVerb(strPinVerb)
' Pin Windows Media Player shortcut to Start menu
Set objFolder = Shell.Namespace(ssfPROGRAMS)
Set objFolderItem = objFolder.ParseName("Windows Media Player.lnk")
objFolderItem.InvokeVerb(strPinVerb)
' Pin Windows Messenger shortcut to Start menu
Set objFolder = Shell.Namespace(ssfCOMMONPROGRAMS)
Set objFolderItem = objFolder.ParseName("Windows Messenger.lnk")
objFolderItem.InvokeVerb(strPinVerb)
' Delete script when done
On Error Resume Next
Set objFolder = Shell.Namespace(ssfSTARTUP)
Set objFolderItem = objFolder.ParseName("pin_explorer.vbs")
Set File = FSO.GetFile(objFolderItem.Path)
File.Delete(true)
On Error Goto 0
Have fun

Place script in USER STARTUP Folder. When I tried running the script from HKCU\SOFTWARE\Microsoft
CurrentVersion\RunOnce the wscript.exe was called but did nothing. I think Microsoft disabled this option to prevent any virusses to launch automaticly at startup.
I like this method, since changing shortcuts is simple and works on different platforms. Didn't test this script on Vista though.
Anyway I spend alot of time on it to get it to work also for subdirs. VBScript is nice, but I prefer AutoIT.
UPDATE: Script only gets deleted from User startup dir now.