Segundo a gramática tradicional brasileira (visão esmagadoramente majoritária), quando um adjetivo, com função de adjunto adnominal*, antecipa dois ou mais substantivos, a concordância nominal se dá com o primeiro elemento. Logo, segundo a norma-padrão brasileira, o certo é «Tudo na mais perfeita paz e ordem».

Sempre às ordens!

* Por ser brasileiro o consulente, adotou-se na explicação a nomenclatura gramatical brasileira.