As construções «Fiz-lhe perder tempo» e «Fi-lo perder tempo» estão ambas corretas.

Os verbos causativos (como fazer ou deixar) ou os verbos de perceção (como ouvir ou ver) admitem vários tipos de construção: 

(i) a elevação do sujeito para objeto

Em algumas situações, os verbos causativos ou de perceção selecionam como complemento direto uma oração (subordinada completiva), que pode ser infinitiva. Nesta situação, e se atentarmos nas frases apresentadas pelo consulente, a orações que estão na sua base da formação serão: 

(1) «[Eu fiz] [o senhor perde tempo].»

Quando a oração subordinada tem o verbo no infinitivo, o seu sujeito passa a complemento direto do verbo da oração subordinante, o que fica patente no facto de o pronome que substitui o sujeito assumir a forma acusativa, ligando-se ao verbo principal. Este fenómeno designa-se elevação do sujeito para objeto: 

(2) «Eu fi-lo perder tempo.»

(ii) a união de orações

é possível também algumas orações subordinadas com verbos no infinitivo integrarem a construção designada união de orações, que corresponde a uma associação entre um verbo causativo (como fazer ou deixar) ou um verbo de perceção (como ouvir ou ver) e uma oração com verbo no infinitivo¹. No caso particular da união de orações, a ligação do verbo causativo ao verbo no infinitivo é tão estreita que se forma um núcleo verbal complexo, que leva a que a frase resultante da união de orações corresponda a uma única oração. O facto de estarmos perante uma única oração obriga a que se proceda a um reajustamento das funções sintáticas, pois numa mesma frase não podem coexistir dois sujeitos (no caso de (1), eu e «o senhor»). Por esta razão, embora «o senhor» se mantenha sujeito semântico de «perder tempo», passa a desempenhar a função de complemento indireto:

(3) «Eu fiz perder tempo ao senhor.»

Se o constituinte «ao senhor» for substituído por um pronome clítico, este terá a forma dativa lhe, a forma de complemento indireto, e será colocado junto ao primeiro verbo do complexo, uma vez que não estamos perante duas orações, mas apenas uma:

(3) «Eu fiz-lhe perder tempo.»

Disponha sempre!

1. Esta construção está descrita em Barbosa e Raposo in Raposo et al., Gramática do Português. Fundação Calouste Gulbenkian, pp. 1961-1966.