Acabei de encontrar o seguinte comportamento:

for (var i = 0; i < 50; ++i) {
    Task.Factory.StartNew(() => {
        Debug.Print("Error: " + i.ToString());
    });
}

Resultará em uma série de "Error: x", onde a maioria dos x são iguais a 50.

Similarmente:

var a = "Before";
var task = new Task(() => Debug.Print("Using value: " + a));
a = "After";
task.Start();

Irá resultar em "Using value: After".

Isso significa claramente que a concatenação na expressão lambda não ocorre imediatamente. Como é possível usar uma cópia da variável externa na expressão lambda, no momento em que a expressão é declarada? O seguinte não funcionará melhor (o que não é necessariamente incoerente, admito):

var a = "Before";
var task = new Task(() => {
    var a2 = a;
    Debug.Print("Using value: " + a2);
});
a = "After";
task.Start();