You may have come across this concept already, but this is where clean rooms come in.

One person views the "contaminated" decompiled code and writes a specification. A separate person writes the code based solely on the specification. This is an accepted method of demonstrating that there is no infringement.

Yep, I knew of clean-room reimplementations, I was just wondering whether decompiling is somehow in itself illegal.

But disassembling/decompiling doesn't give you anything like the original code!

It gives you a derivative work of the original code

That kind of depends on the language, but it's a fair point. I think it might only matter that the general algorithm/solution is the same, not the lines of text themselves.