Maybe after a year, you lost interest, but maybe other people want a solution for this problem too... And there IS a (very simple) solution
The post of --dp-- made me think and try.
In fact, Windows isn't that "smart", it's all about setting the properties of the ".lnk-file", so I'll try to explain.
Suppose that you have file start.exe on your flashdrive in folder '\Program' (subfolder from the root) on drive D: and you want to make a shortcut that works on any other drive. Right click on the file start.exe and choose "create shortcut".
Move that shortcut in the root. You may rename it if you want. The program will, naturally, start because the shortcut refers to absolute location (path) of the start.exe.
Now, look at start.lnk (right click, properties). Erase everything in the second box from the top (Next to it says: "Start in:" or "Begin in:"... I'm not sure, because my pc is Dutch)
Now your shortcut works on every pc, with every drive letter!
Note: if the drive letter changes, the shortcut won't have the program's icon until you click on it... but that's not the most important thing