Добре - ще се опитам да отговоря на собствения си въпрос. Това е най-доброто, което мога да измисля:
Опаковка:
$binary = pack("h*", str_replace('-', '', $string));
Разопаковайте
$string = unpack("h*", $binary);
$string = preg_replace("/([0-9a-f]{8})([0-9a-f]{4})([0-9a-f]{4})([0-9a-f]{4})([0-9a-f]{12})/", "$1-$2-$3-$4-$5", $string);
Има ли някакъв проблем с това, който някой може да види?