How can I redirect all shortcuts to a given executable? Is there any equivalent to a symlink on Windows?

Question

I am working on a program which includes a general purpose engine, some program specific content, and a custom automatic updater to handle updating the many gigabytes worth of media in our content as efficiently as possible. In a recent release of the engine, we have reorganized our directory structure, such that instead of the executable installing to (for example) c:\Program Files\Program\Engine.exe, it is now in c:\Program Files\Program\engine\win32\NewEngine.exe (note that the name of the engine changed as well in this process).

The problem is that in order to launch the program, the user needs to use a shortcut, which we install in their start menu and (optionally) on their desktop. The move of the engine after an update breaks those shortcuts, though. So now I need to figure out a way to fix all of the shortcuts that the user has in order to launch the program.

Coming from a Unix/Mac OS X background, my inclination would be to just create a symlink from the old executable name to the new one. As far as I know though, there isn't really an equivalent of a symlink on Windows (from Googling, I see that there are symlinks on Vista and later, but this needs to work on XP). Am I wrong in my assumption? Is there any equivalent on Windows to a symlink to an executable?

Some other possible solutions that come to mind are:

1. Creating a small executable at the old location that launches the real one in the new location. Is there any quick and easy way to create a simple, headless executable, that just launches another program? Again, on Unix, I'd simply create a shell script, but as far as I know I can't name a .bat file .exe and have it run, so this needs to be a way to actually generate an .exe.
2. Upon the update, search for all shortcuts that point to the executable and edit them. Is there any (efficient and reliable) way to find all shortcuts on the system that point to a given location and update them?
3. A combination of the above, with a small executable that detects that it's being launched from a shortcut, and edits that shortcut before launching the real program. Is there any way to detect that a program is being launched from a shortcut, and thus be able to edit that shortcut?

Would any of these options work, and if so how? What is the best way to do this sort of thing on Windows? Am I missing any other ways of redirecting a shortcut from one location to another?

edit to add: Some additional requirements we have:

1. Many of our users are non-technical. Any solution requiring user intervention is out of the question.
2. This should be as seamless as possible. Having any extra windows pop up every time the user clicks the shortcut is unacceptable.
3. This should be robust in the face of most things the user could have done, such as rearranging their start menu or moving a shortcut to the quick launch bar.
4. Our shortcuts are absolutely necessary to the functioning of the program, as they pass in arguments necessary for the engine to load the content (yes, this is less than ideal; I would prefer to fix this, but cannot at this point)
5. I'm looking for something that is relatively quick and easy to implement and extremely reliable.

Answer 1

Well, the solution we've decided on is just doing the small little executable that launches our real engine. It took a bit more futzing with Visual Studio to get the project set up than I would have preferred, but it seems to be working out.

#include "stdafx.h"
#include <shellapi.h>

int APIENTRY _tWinMain(HINSTANCE hInstance,
                       HINSTANCE hPrevInstance,
                       LPTSTR    lpCmdLine,
                       int       nCmdShow)
{
  HINSTANCE result = ShellExecute(NULL, _T("open"), 
                                  _T("engine\\win32\\NewEngine.exe"),
                                  lpCmdLine, NULL, 1);
  // ... handle errors ...
  return 0;
}

edit: Nope. This seems to work on XP, but not Windows 7 or Vista. Any ideas for why this would fail on Windows 7 or Vista would be much appreciated. If I can't figure this out soon, I may break this out into a separate question.

edit 2: Ah. On XP, forward slashes in the pathname work just fine. On Vista or newer, you need backslashes.