DPD - Entrega e encomenda perdida

Dia 21/12 tentaram fazer a entrega da minha encomenda, estando eu em casa, incrivelmente não ouvi a campainha tocar nem bater à porta. No registo do vosso site informa que não me encontrava no local e a encomenda iria voltar ao armazém.
A última referência do tracking code é o retorno da mesma encomenda ao armazém datada de dia 22/12.
Hoje dia 15/1, continuo sem ter informações da minha encomenda e seu paradeiro.
Dirigi-me 2 vezes à loja dos Olivais para tentar recolher ou resolver a situação, infelizmente a funcionária que se encontra ao balcão foi bastante rude e informou-me das 2 vezes que a encomenda estava a retornar ao armazém. A última vez que me dirigi ao vosso balcão foi dia 13/1, tendo eu questionado a mesma funcionária e ela respondendo que achava normal a demora.
Deixo aqui o meu total desagrado sobre a situação, desculpas não são suficientes pois a prenda era uma prenda de Natal.
Quero a situação resolvida porque é inaceitável uma encomenda estar quase 1 mês para dar "entrada" numa armazém e voltar a ser entregue.

Boa tarde,

Já passaram 5 dias e ainda não obtive nenhum feedback. A primeira tentativa de entrega como referi foi dia 21/12 faz amanhã 1 mês.
Como devem calcular a desculpa do Natal / Ano Novo já não é suficiente visto que já passaram 20 dias desde o início do ano.
Gostava de colocar uma questão, os senhores já foram pagos pela entrega, correto?
Mas eu lamentavelmente ainda não a tenho a minha "prenda" e as minhas expectativas foram completamente defraudadas devido ao vosso péssimo serviço.

Cumprimentos,

Miguel
Aguardo uma resposta da vossa parte o mais rapidamente possível.

Gostava de referir que continuo sem qualquer tipo de contacto da vossa parte ou solução para o problema.
Se até dia 31 de Janeiro, não tiver o meu problema resolvido serei obrigado a contactar as autoridades legais.
De referir este artigo https://www.anacom-consumidor.pt/distribuição postal
A parte :
"Atraso ou extravio de correio internacional

No correio internacional, em caso de extravio, furto ou dano de objetos enviados em correio registado, o remetente tem direito a uma indemnização cujo montante máximo corresponde a:

cerca de 34,75€ na correspondência registada; e
cerca de 46,33€ nas encomendas, acrescida de cerca de 5,21€ por cada kg.
Não há direito a indemnização nos casos de extravio, furto ou dano de correio não registado, bem como em caso de atraso do correio."

Com os melhores cumprimentos,

Miguel

Recebi uma actualização disseram que tinham entregado a encomenda, mas foi na Madeira, a minha morada é em Lisboa.
Pelo que parece a Dpd usa o mesmo tracking code para várias encomendas.
Inaceitável este tipo de serviço, ainda não fui contactado por ninguém.

Continuo sem qualquer resposta por parte da Dpd