Thanks for all the replies, I've discovered what was doing it and feel like an utter fool now. IOBit the guys who make Smart Defrag also make a tool called Advanced SystemCare Pro which has a scan to get rid of spyware, registry errors and temp files.
As your probably guessing that was the culprit. And most annoyingly about 5 of my apps have had their links deleted not only from my desktop folders (I have specific folders on my desktop for Games, Apps etc), but also from the Start menu. I've manually gone back and created shortcuts to these apps I lost but its bloody annoying. Things like Sony Vegas Pro 9.0 loosing all of its start menu links is pretty irritating as I'm more than certain that came with a bunch of different shortcuts, not just for the Application itself but extra features too - and these shortcuts I'll never remember to get back.
I could go back and reinstall these Apps which is easy for Paint.net, but for things like Sony Vegas and ESET Smart Security its a downright pain in the arse.
So moral of the story - avoid using Advanced SystemCare Pro. Although I'm sure it removed some rubbish it also removed useful links. I'm unsure if this is an issue with it + Windows 7, or for all versions of Windows, but I would personally recommend to stay clear of it. Hope this helps someone for future reference.