El problema es que aplicas str_replace() sobre todo el texto, cuando deberías hacerlo linea por linea.
Con file() puedes cargar el archivo en un array, y con implode() puede volver a unirlo por saltos de linea, con foreach() creas el loop y el resto ya sabes hacerlo.