I think they were short of time (as the post mentions, everything Lekktor happened within a single week; this is the most impressive part of the entire post) and had rather special build environments that are unsuitable for many profilers. For example the kkrunchy executable packer [1] used by Farbrausch doesn't pack the DLL sections at all, so any instrumention relying on them will be ruined. Such things.
I get that, but even the simpler side of the instrumentation tools we used wouldn't have been a problem to use for them. The most basic one basically just (with knowledge of the language) inserted outputs at function entry/exit and branch points (if, else, loops). However, it was a commercial tool that did this for us as part of their suite of tools. I have no idea what the status of open source/free tools would have been in 2004 to do the same thing.
[1] http://www.farbrausch.de/~fg/kkrunchy/