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