This "new" product from MS is not actually new... MS recently (about a month ago) bought out Giant Antispyware - which was a fairly good antispyware product - but it wasn't free like AdAware or Spybot Search and Destroy. After the purchase was announced, most downloadable versions of the software were taken down (you can still find the original installer if you know where to look). Having just looked at this piece of software from Microsoft, it's seems to be exactly the same piece of software, just rebranded with Microsoft instead of Giant.
Not sure, personally, as I haven't really had any spyware on my machine to say how effective it is at removing them (probably because I surf with Firefox and Opera and never use IE) - but I've read reviews of Giant AntiSpyware and people mention that it can be more effective than AdAware and Spybot at detecting and removing certain things. Whether that's true or not, I can't say.
I find it funny how it's the buggy POS software that is IE that is the main cause of spyware on machines and MS decide to bring out an antispyware product instead of fixing IE. Wonder if they'll charge people for it in future, since this is released as a beta.
I'm using the Giant antispyware in my line of work. Honestly speaking, it is much better than adaware and spybot combined. It removes proxy jackers and marketscore better than any other antispyware program i've tested before.