Regex con posibles partidos vacíos y partido multilínea

He estado tratando de"analizar gramaticalmente" algunos datos utilizando una expresión regular, y me siento como si estuviera cerca, pero parece que no puedo llevarlo todo a casa.
Los datos que necesitan análisis generalmente se ven así:<param>: <value>\n. El número de parámetros puede variar, al igual que el valor. Aún así, aquí hay un ejemplo:

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 empujar este texto en un objeto, junté esta pequeña expresión

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);
}

Ahora, esto funciona bien la mayor parte del tiempo, excepto por elUser Message poco:. No coincide con las nuevas líneas, porque si tuviera que usar els bandera, el segundo grupo coincidiría con todo despuésFooID: hasta el final de la cadena.
Tengo que usar una solución sucia para eso:

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

Después de algunas pruebas, he llegado a comprender que, a veces, uno o dos de los parámetros no se completan (por ejemplo, elInternalID puede estar vacío). En ese caso, mi expresión no falla, sino que resulta en:

    [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,
        )

He estado probando varias otras expresiones, y se me ocurrió esto:

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

La segunda versión es un poco más lenta.
Eso resuelve los problemas que tuve conInternalID: <void>, pero aun así me deja con el último obstáculo:User Message: <multi-line>. Utilizando las bandera no hace el truco con mi expresión ATM.
Solo puedo pensar en esto:

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

Lo cual es, al menos para mi ojo, demasiado complejo para ser la única opción. Ideas, sugerencias, enlaces, ... cualquier cosa sería muy apreciada.

Respuestas a la pregunta(4)

Su respuesta a la pregunta