You already asked this question over at Microsoft and they advised you to come here ... nevertheless the Microsoft guy did point you towards a removal guide from Malwaretips.
This is adware, but a particularly nasty variety of adware. McAfee detects it (according to VirusTotal) as "Artemis!719AD5D66260".
You can either go ahead and use the Malwaretips removal advice now, or submit this first to the McAfee Labs for analysis. Since the .exe file is not the only one that this adware puts on your system you should run GetSusp, which will send any suspect files it finds for testing. It doesn't remove them, but that gives you an idea of what to remove.
Download GetSusp from http://www.mcafee.com/us/downloads/free-tools/getsusp.aspx
Instructions for its use are at http://www.mcafee.com/us/downloads/free-tools/how-to-use-getsusp.aspx
Malwarebytes and AdwCleaner between them should remove most of the traces of the adware. Don't edit the registry (as some people advise) unless you really know what you're doing.
Microsoft had a previous enquiry about this adware a year ago - I'm surprised the person who answered you didn't find it.