Transforming a binary matrix into triangular form using permutation matrices

Luckily, the problem is no more in the "NP-limbo". The paper Obtaining a triangular matrix by independent row-column permutations Fertin, Rusu, and Vialette shows that the problem is NP-complete for binary square matrices.

EDIT: Also, the same problem was asked five years ago on CS Theory StackExchange and it was proven to be NP-complete. Here is the published version, Topological orderings of weighted directed acyclic graphs, by Gerbner, Keszegh, Palmer, and Pálvölgyi

This problem was studied by Knuth's PhD student Ramsey W. Haddad in his thesis: Triangularization: A Two-Processor Scheduling Problem.

According to the thesis, the problem is in the "NP-limbo" (not known to be NP-complete or in P). The thesis was published in 1990, which is prior to the reference you mention. However, it contains a lot of observations on the problem and the complexity analysis of some extensions of the problem, which may be of your interest.

Also, you may be able to track up new references starting from there.