The problem with something like this is that no antimalware or antivirus programmes will detect it. Hence all the manual searches
I do not believe that the shortcuts are infected but we can try this next
Could you download and run short cut cleaner from here http://www.bleepingcomputer.com/download/shortcut-cleaner/
Once done could you post the log