I can't find anything specific about how similar new binary should be to be to not get into trouble. For now it's probably case by case. You are correct that you can't legally redistribute unmodified binary.

I can only judge from the cases I know about regarding videogames. The two instances where publishers decided to intervene via a cease and desist letter or DMCA takedown: fan-made Metroid 2 remake (AM2R) and reverse engineering of GTA 3/Vice City/San Andreas. Both Nintendo and Take-Two were making their own remakes of those games at the time, so they probably saw it as a threat to their profits.

But a lot of decompilations and ports have been made without any intervention from the publishers (at least from my knowledge). Diablo 1 has both a decompilation (code and exe) and a port. N64's Zeldas also have both, which is interesting since Nintendo is known for issuing DMCAs, and they also have a remake of Ocarina of Time currently in the works, so there should be enough reason to take down such projects (like they did with Metroid 2). I assume they are not doing anything because it's just the binary being distributed.