Olá menino Paulo!
Que bom que tu gostou do reultado do "Tris to Quad". Realmente, trabalhar com malhas muito densas é terrível.
Fiz um breve teste aqui e posto os resultados pra tu ver:
01 - O STL que baixei, originalmente com 30351 vértices e 60520 faces.

Tutorial de retopologia de um relevo STL com 3D Coat
02 - A malha em tris, realmente bastante densa.

Tutorial de retopologia de um relevo STL com 3D Coat
03 - O STL após a aplicação de um modificador Decimate em 0.15 de fator. Agora com 4580 vértices e 9078 faces.

Tutorial de retopologia de um relevo STL com 3D Coat
04 - A malha após a aplicação do Decimate.

Tutorial de retopologia de um relevo STL com 3D Coat
05 - A malha após a aplicação da função Tris to Quad. Agora ainda com 4580 vértices e com 5961 faces.

Tutorial de retopologia de um relevo STL com 3D Coat
06 - O STL após o processo, não cheguei a editar os tris restantantes, pois só queria testar o resultado rapidamente.

Tutorial de retopologia de um relevo STL com 3D Coat
Dá pra perceber que tivemos uma perda aceitável nos detalhes do modelo, e óbviamente, pra nós que gostamos de modelar ver uma malha totalmente desorganizada assim chega a dar calafrios, hehehe...
Claro que com uma retopologia temos um resultado bem melhor, mas acho que em determinadas situações poder contar com estas funcionalidades é ótimo!
Na minha carroça o processo não levou mais que 3 minutos, mas não sei exatamente o número de vértices e faces do teu modelo. Há de se levar em conta, também, os novos algorítmos do Blender 2.58, que foram reescritos.
Partimos de 30351 vértices e finalizamos com 4580, uma redução de +- 85%. E de 60520 faces e finalizamos com 5961 (sem editar os tris restantes), uma redução de +- 90%.
Quanto ao patch do menino Novak, para criar bas relief, foi justamente por ele que acabei conhecendo o Blender, hehe... Na época eu estava justamente pesquisando uma ferramenta para me ajudar na facilitação do processo de criar relevos, hehehe....
Mas até onde sei não foi re-lançado para as versões 2.5x, pena...

Bem menino Paulo, espero que as informações tenham alguma utilidade e vamos continuar "trocando figurinhas", pois percebo que teus estudos estão caminhando na mesma linha que os meus.

Grande Abraço e Muita PAZ!
Elton "Velho Hippie" Ribeiro