The search in my copy of Win 8 can't seem to find any shortcuts except those in the Start Menu folder.
Using the search in the Start screen.
I did this to test:
1) Create a shortcut at an indexed location thats not the Start Menu folders
2) I waited a bit and notice the item count in the "Indexing Options" increase by one
3) Went to search for the shortcut at the Start screen search
And I can't find the shortcut.
I tried the search in Start8 and Pokki too but it seems that they use the Win 8 search as well.
What does work is the search field at the top right of the File Explorer, Launchy works too.
And also it worked in Win 7 as well.