e4 75
é de fato uma sequência utf8 ilegal. No utf8, um byte com o nibble mais alto igual a 0xe introduz uma sequência de três bytes. O segundo byte de tal seqüência não pode ser 0x75, porque o nibble de alta ordem desse segundo byte (0x7) não está entre 0x8 e 0xb.
Isso explica porque o iconv rejeita esse arquivo como utf8 inválido. Talvez já seja iso8859-1?
Para um resumo da codificação utf8, consulte esta tabela da Wikipédia
Quanto ao seu problema com o grep, talvez se você especificar o código do idioma C / POSIX, onde os caracteres são equivalentes a bytes:
LC_ALL=C grep -P -n '[^\x00-\x7F]' corrupt_part.txt
Usando um antigo sistema Ubuntu, o GNU grep e um ambiente usando o código do idioma en_US.UTF-8:
$ od -h bytes
0000000 624f 7265 6c61 676c 75e4 0a20
0000014
$ grep -P '[^\x00-\x7F]' bytes | od -h
0000000 624f 7265 6c61 676c 75e4 0a20
0000014
$ LC_ALL=C grep -P '[^\x00-\x7F]' bytes | od -h
0000000 624f 7265 6c61 676c 75e4 0a20
0000014