>> (в hex представлении), а в начале \xE3\x33 но при этом он
>> не всегда находится в самом начале иногда перед ним бывает 1
>> или 2 символа. При этом длинна "мусорной" строки всегда 70 байт.
> Этому определению строки строго соответствует регексп

(?=.{0,2}\xE3\x33).{68}\x00{2}

> Дальше понятно, или нужно разжевывать?

Ага. Разжуй две ситуации, в которых твой regex не сработал:
   1. Перед \xE3\x33 есть ОДИН символ
   2. Перед \xE3\x33 есть ДВА символа. Строка осталась 70 байтов. А ты ожидаешь 72.