Olá...
vi diversas possibilidades de melhoria no desempenho do seu código.
Apliquei:
1) uso de matrizes
2) uso correto de estruturas de repetição
3) excesso de métodos do objeto range sendo disparados
4) excesso de propriedades do objeto range sendo lidos
5) aproveitei o conceito do Union para não deletar todas as linhas de uma só vez, ao invés disso, todas elas são acumuladas num objeto do tipo range, e deletadas ao final dos processos...

Enfim, ainda tem espaço pra mais melhorias... mas eu acho que já melhorei bastante.

Sua macro demora cerca de 1h pra rodar? Bom, não fiz o teste do tempo total aqui no meu micro, pq não tenho tempo pra isso...
MAS, eu uso um Xeon E5630 2.52ghZ, com 2GB de RAM e Windows 8 32 bits.
O tempo final de execução após a aplicações das melhorias foi de 30segundos.

Espero que isso esteja bom pra vc, rs