<?php
$string ='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
Yellow:cool';
 
$array = array();
preg_replace_callback('#^(.*?):(.*)|.*$#m', function($m)use(&$array){
    static $last_key = '';
	if(isset($m[1])){
		$array[$m[1]] = $m[2];
		$last_key = $m[1];
	}else{
		$array[$last_key] .= PHP_EOL . $m[0];
	}
}, $string);
print_r($array);
?>

PD9waHAKJHN0cmluZyA9J0Zvb0lEOiAxMjM0NTYKTmFtZTogQ2h1Y2sKV2hlbjogMDEvMDIvMjAxMyAwMToyMzo0NQpJbnRlcm5hbElEOiA3ODk2NTQKVXNlciBNZXNzYWdlOiBIZWxsbywKdGhpcyBpcyBuaWxsYWJsZSwgYnV0IGNhbiBiZSBxdWl0ZSBsb25nLiBUZXh0IGNhbiBiZSBzcHJlYWQgb3V0IG92ZXIgbWFueSBsaW5lcwpBbmQgY2FuIHN0YXJ0IHdpdGggYW55IG51bWJlciBvZiBcblwncy4gSXQgY2FuIGJlIGVtcHR5LCB0b28KWWVsbG93OmNvb2wnOwoKJGFycmF5ID0gYXJyYXkoKTsKcHJlZ19yZXBsYWNlX2NhbGxiYWNrKCcjXiguKj8pOiguKil8LiokI20nLCBmdW5jdGlvbigkbSl1c2UoJiRhcnJheSl7CiAgICBzdGF0aWMgJGxhc3Rfa2V5ID0gJyc7CglpZihpc3NldCgkbVsxXSkpewoJCSRhcnJheVskbVsxXV0gPSAkbVsyXTsKCQkkbGFzdF9rZXkgPSAkbVsxXTsKCX1lbHNlewoJCSRhcnJheVskbGFzdF9rZXldIC49IFBIUF9FT0wgLiAkbVswXTsKCX0KfSwgJHN0cmluZyk7CnByaW50X3IoJGFycmF5KTsKPz4=