Portable Shortcuts on Windows

I can’t figure out how to create shortcuts that don’t care where they are mounted.  For example, on my flash drive, I want to run CCleaner or Notepad++ in my college classroom.  The problem is, a shortcut (at least with default settings) doesn’t work reliably because it is tied to the same drive it was created on.  Is there a way to do something like in HTML?  

Example:

Here is where the actual program is:

RootPortable ApplicationsProgram DataCCleanerccleaner.exe

Here is where I want the shortcut to be:

RootPortable ApplicationsCCleaner.lnk

U3/Portable Apps/etc is not the solution I am looking for

Edit: The Versions of Windows will be XP 32 bit, Vista 64 bit, and Vista 32 bit

Solution:

You can use mklink if on Vista or later to create symbolic links. They can be pointed to wherever you want. Alternatively a batch file as pointed out by pelms would work as well.