>> Е> Что-то такое, если я вас верно понял.
> $clean = do{ use bytes ; $str =~ s/.{68}\x00{2}(?!=\x00)//g ; $str }

Так оно не проверит на \xE3\x33. Нужно тщательнее:

$clean = do{ use bytes;
  $str =~ s/\xE3\x33.{66}\x00{2}//og;
  $str =~ s/.\xE3\x33.{65}\x00{2}//og;
  $str =~ s/..\xE3\x33.{64}\x00{2}//og;
  $str }

Три простых регекса отработают в разы быстрее одного сложного.