Um artigo que eu li mês passado, tem até site próprio, Logging Sucks (ING) fala sobre isso.

Basicamente, em vez de fazer um log de cada parte durante a operação, você faz um evento que é incrementado durante a operação, dentro do contexto da requisição, só pra no final fazer log da requisição como um todo.

Vale a pena dar uma lida.