The various MSR labs are looking for postdocs and full-time researchers in many scientific fields, including all areas of theoretical Computer Science. You can apply via this website. Please don’t forget to specify in the form all the labs you may be interested in.
For Microsoft Research Silicon Valley applications submitted by December first will receive full consideration.
The deadline for the Schramm Postdoctoral Fellowship (joint with MIT math and Microsoft Research New England) is also on December first.
As Omer says: dont trust the machine. Make sure that somebody relevant knows you are applying.
Windows On Theory 