The list below contains the open problems presented at Microsoft Research Theory Lunch.
A list of open problems for internal access only can be found here

2012:

May 24	Questions from Alexander Holroyd on perfect shuffling by random transpositions (see PDF)
May 17	Questions from Chandra Chekuri on complexity of submodular partitioning (see PDF)
February 15	Questions from Roberto Imbuzeiro Oliveira on the cat-and-mouse game (see PDF) and Serguei Popov on the range of many-dimensional martingales (see PDF)

2011:

October 5	Questions from Pawel Pralat on the firefighter problem (see PDF) and Nicolas Curien on Rémy's algorithm for generating random binary trees (see PDF)
September 28	Questions from Pawel Pralat on the cops and robbers problem (see PDF)
September 14	Questions from Ben Morris (see PDF)
September 7	Questions from Peter Winkler (see PDF)
August 31	Questions from Alexandre Stauffer on balls and bins (see PDF)