This test with Notepad works for me :
(I replaced TargetPath with a .exe with spaces in the path and it worked...)
' Add reference to Windows Script Host Object Model
' Add Imports IWshRuntimeLibrary
Dim shell As New WshShell()
Dim sDesktopPath As String = Environment.GetFolderPath(Environment.SpecialFolder.Desktop)
Dim sShortcutPath As String = Path.Combine(sDesktopPath, "NotepadShortcut.lnk")
Dim shortcut As IWshShortcut = CType(shell.CreateShortcut(sShortcutPath), IWshShortcut)
shortcut.TargetPath = """C:\Windows\System32\notepad.exe"""
shortcut.Arguments = """e:\Test file.txt"""
shortcut.WorkingDirectory = "C:\Windows\System32"
shortcut.IconLocation = "C:\Windows\System32\notepad.exe, 0"
shortcut.Save()