Correct, both the technique described in that article and the feature that eventually wound up in GNU make only disentangle output from concurrently executing build processes. With significantly more work GNU make could probably be made to enforce a deterministic order.
However, Electric Make does emit the output in a deterministic order, in fact in exactly the same order as the build would have produced had it run serially. In practice the delayed output is not such a big deal -- people just don't really seem to care that much, when the build overall finishes 20x - 30x faster than it used to. Electric Make also generates an annotated build log, essentially an XML-marked-up version of the log, which contains a tremendous amount of additional information about the build and vastly simplifies debugging, actually.
However, Electric Make does emit the output in a deterministic order, in fact in exactly the same order as the build would have produced had it run serially. In practice the delayed output is not such a big deal -- people just don't really seem to care that much, when the build overall finishes 20x - 30x faster than it used to. Electric Make also generates an annotated build log, essentially an XML-marked-up version of the log, which contains a tremendous amount of additional information about the build and vastly simplifies debugging, actually.