Regex com possíveis partidas vazias e partida multi-line

Eu tenho tentado"parse" alguns dados usando um regex, e sinto como se estivesse perto, mas não consigo levar tudo para casa.
Os dados que precisam de análise geralmente se parecem com isso:<param>: <value>\n. O número de parâmetros pode variar, assim como o valor pode. Ainda assim, aqui está um exemplo:

FooID: 123456
Name: Chuck
When: 01/02/2013 01:23:45
InternalID: 789654
User Message: Hello,
this is nillable, but can be quite long. Text can be spread out over many lines
And can start with any number of \n's. It can be empty, too.
What's worse, though is that this CAN contain colons (but they're _"escaped"_ using `\`), and even basic markup!

Para empurrar este texto para um objeto, eu juntei esta pequena expressão

if (preg_match_all('/^([^:\n\\]+):\s*(.+)/m', $this->structuredMessage, $data))
{
    $data = array_combine($data[1], $data[2]);
    //$data is assoc array FooID => 123456, Name => Chuck, ...
    $report = new Report($data);
}

Agora, isso funciona bem a maior parte do tempo, exceto peloUser Message pouco:. não corresponde a novas linhas, porque se eu fosse usar os bandeira, o segundo grupo iria corresponder tudo depoisFooID: até o final da corda.
Eu estou tendo que usar uma solução suja para isso:

$msg = explode(end($data[1], $string);
$data[2][count($data[2])-1] = array_pop($msg);

Depois de alguns testes, cheguei a entender que, às vezes, um ou dois dos parâmetros não são preenchidos (por exemplo,InternalID pode estar vazio). Nesse caso, minha expressão não falha, mas resulta em:

    [1] => Array
        (
            [0] => FooID
            [1] => Name
            [2] => When
            [3] => InternalID
        )

    [2] => Array
        (
            [0] => 123465
            [1] => Chuck
            [2] => 01/02/2013 01:23:45
            [3] => User Comment: Hello,
        )

Eu tenho tentado várias outras expressões e descobri isso:

/^([^:\n\\]++)\s{0,}:(.*+)(?!^[^:\n\\]++\s{0,}:)/m
//or:
/^([^:\n\\]+)\s{0,}:(.*)(?!^[^:\\\n]+\s{0,}:)/m

A segunda versão é um pouco mais lenta.
Isso resolve os problemas que tive comInternalID: <void>, mas ainda me deixa com o obstáculo final:User Message: <multi-line>. Usando os flag não faz o truque com a minha expressão ATM.
Eu só posso pensar nisso:

^([^:\n\\]++)\s{0,}:((\n(?![^\n:\\]++\s{0,}:)|.)*+)

Que é, pelo menos aos meus olhos, complexa demais para ser a única opção. Idéias, sugestões, links, ... tudo seria muito apreciado

questionAnswers(4)

yourAnswerToTheQuestion