Fiz este interface para obter a informação do site dos correios de uma forma estruturada. Pode ser útil para integrar em projectos de e-commerce nacionais. Suporta JSON, JSONP, XML e SOAP.

Mais detalhes em:
http://www.pesquisarencomendas.com/api

Bom projecto! Pode ser que dê jeito no futuro!
(cliquei na pub. como forma de agradecimento )

Uma sugestão, o site poderia estar com um design mais apelativo e não tão grande. De resto é uma ferramenta útil, embora já exista um site parecido que até permite o envio de actualizações por email.

Qual é esse site?

Desconhecia, está muito porreiro. O feature de notificação por email é uma boa ideia, e não é dificil implementar.
Tem apenas uma desvantagem que é não ter uma API que permita a integração simples noutros sites, que foi o meu objectivo principal