Do user-specified shortcut keys for Windows only work on certain directories?

It must be in the Start menu folders or the Desktop.

As per the Microsoft Support page, Shortcut key for shortcut does not work:

Symptoms

You are unable to run a shortcut by pressing its shortcut key.

Cause

Shortcut keys work only for shortcuts on the desktop or in the Start menu hierarchy.

Resolution

Make sure that the shortcuts for which you want to use shortcut keys are on the desktop, on the Start menu, or in the Windows\Start Menu\Programs folder.

More Information

Shortcut keys work differently depending on the location of the shortcut. If the shortcut is on the desktop or in the Start menu hierarchy, you can use its shortcut key to start the assigned program, or switch to the program if it is already running.

If the shortcut is not on the desktop or in the Start menu hierarchy, you cannot use its shortcut key to start the assigned program, but you can use its shortcut key to switch to the assigned program if it is already running.

NOTE: Shortcut keys may not work for some programs. For example, shortcut keys do not work for items on the Quick Launch bar.

I guess the problem comes from the fact that Windows will only scan certain directories for links and their keyboard shortcuts. The folders you have mentioned, and where the keyboard command does not work, will most likely be not "scanned" by Windows.

I have found this KB entry for Windows XP where it says that this type of keyboard shortcuts only work for links on the Desktop and inside the Start menu. For Windows 7, I found this entry but it does not specify in which folder the link needs to be.

However, I can confirm that the keyboard shortcut will work when the entry is inside Programs of the start menu.

Therefore, I would suggest that you simply drag and drop the link to the Programs menu, then assign the shortcut again to make sure Windows knows about it and it should work as expected.