In the United States, a determination of copyright infringement is based on two broad considerations:
- the author's access to the original work
- the new work's similarity to the original work
If you choose to re-implement some software without ever viewing its source code, then you can nullify the first consideration and avoid infringement (provided you can successfully prove the negative of never having seen the source code). This is the "clean room" approach to re-implementing software.
If you have looked at the original work, though, we must examine the second consideration. What makes one written work "similar" to another in copyright terms?
Copyright applies to creative expression. Ideas are ineligible for copyright, per the idea-expression divide. This is closely related to the "merger doctrine": if an idea can be expressed in a very limited number of ways, then the idea and it only possible expression are considered merged -- the expression is the idea. For example, describing the rules of a game in a purely mechanical way ("Draw one card, then play one card that matches a color on the board...") can only be done in a few reasonable ways.
We know, then, that some aspects of a work are not copyrightable (i.e., those on the "idea" side of the divide), and other aspects are copyrightable (on the "expression" side). A naive hope would be that a complete removal of all original code would eliminate all derivative copyright concerns, but a work can be derivative without actual lexical similarity. That is, the elements of a work that are protected by copyright extend beyond the exact words, or lines of code, or chords of a song.
Consider that literary characters are protected by copyright, and the creation of a new work that uses a copyrighted character -- even absent any infringing text from the original work -- can be infringement. While I am not aware of any relevant case law, there may be analogous considerations for the creative decision-making that goes into writing a computer program. The structure of a program, or the organization of code into files and classes might be sufficiently creative to qualify for copyright protection.
The point here, I suppose, is that it's all a bit murky. In my understanding, if you could theoretically identify all the copyrightable elements of a program and remove them and replace them with your own work, you'd have a work that is no longer a derivative of the original. That is, if you logically strip the program down to its barest idea-from and then build it back up with your own expression, then you have freed yourself from the original copyright. I think this sounds difficult to do feasibly, but it is an approach that might possibly pass in a court of law if you could do it.
If there exists a later work, down a chain of derivatives, that contains no trace of copyrightable elements from the original (including non-literal copyrightable elements), then probably the downstream work is no longer legally a derivative of the original, since it fails the similarity test. I am not prepared to say whether it would be possible to create such a work.