Explorer kann nicht nur Verzeichnisse mit relativen Pfadangaben öffnen, sondern auch Programme ausführen – was darauf hinausläuft, dass es sich bei beidem um Variationen von ShellExecute handelt:
C:\Windows\explorer.exe ..\Ordner2\Beispiel.exe
Alternativ per Shell (Konsolenfenster poppt kurz auf):
C:\Windows\System32\cmd.exe /c start ..\Ordner2\Beispiel.exe
bzw. mit Wechsel des Arbeitsverzeichnis:
C:\Windows\System32\cmd.exe /c cd ..\Ordner2 & start Beispiel.exe
In allen diesen Fällen sollte man beachten, das Feld „Ausführen in“ leer zu lassen, damit die Verknüpfung kein Arbeitsverzeichnis vorgibt und dadurch vom übergeordneten Verzeichnis der Verknüpfung ausgeht – und nicht etwa C:\Windows oder C:\Windows\System32 wie vom Verknüpfungsassistent vorgegeben.
Die Win32-API bzw. die COM-Schnittstelle der Shell hat zwar eine SetRelativePath-Methode, aber diese macht nicht, was man davon erwartet (ist dafür gedacht, den beabsichtigten Pfad zu einer Verknüpfungsdatei anzugeben, wenn man diese nicht mit dem IPersistFile-Interface in eine Datei schreibt, sondern per IPersistStream anderweitig bearbeitet).
Prinzipiell gibt es für das Problem einen Hack. Verknüpfungen speichern üblicherweise immer einen absoluten und relativen Pfad zu ihrem Ziel. Letzterer wird aber in der Regel nicht benutzt, da eine Verknüpfung auch verschiedene Informationen enthält, die es dem Explorer erlauben, das verschobene Ziel einer Verknüpfung wiederzufinden (Kapitel 2.3.1 VolumeID, Seite 22ff. in „[MS-SHLLINK]: Shell Link (.LNK) Binary File Format“). Diese sind in deinem Fall aber völlig missführend, da sie z. B. auch die Seriennummer und Label des Laufwerks enthalten (hier z. B. auf Laufwerk „Windows 10“ auf dem Rechner „spitfire“), auf dem das Ziel abgelegt wurde.

Programmatisch kann man nun das Flag ForceNoLinkInfo (um diese Strukturen zu ignorieren) sowie ForceNoLinkTrack (um ähnliche Strukturen für Vista aufwärts zu ignorieren) gemäß Kapitel 2.1.1 setzen, damit der Explorer bei fehlendem Ziel als nächstes auf den relativen Pfad zurückgreift. Das geht ebenfalls entweder wie oben beschrieben über das COM-Interface – oder indem man den 32-Bit-Integer an Offset 0x14 um die Flags 0x40100 ergänzt. Gegebenfalls schreibe ich im Zug dafür noch ein kleines Programm.