SMS não entregues

Por vezes as sms que mando para um numero não chegam ao destino, no meu telemóvel aparece como "entregue" mas o outro numero nem sequer chega a recebe-la. Tem-me acontecido isto todos os dias e já chegou a acontecer umas 3 vezes no mesmo dia e as vezes até acontece que mando 3 sms seguidas e a outra pessoa não as recebe, acontece aleatoriamente, as vezes recebe outras vezes não. Isto causa-me muito transtorno porque falo todo dia por sms com este numero e já tenho este problema a muito tempo e não consigo resolver. O mais estranho é que a outra pessoa já comprou um telemóvel novo e acontece exactamente o mesmo que acontecia. Eu próprio já formatei o meu equipamento, tem todas as actualizações em dia, já fui a lista de bloqueados no outro equipamento ver se lá estava o meu numero por engano e nada, fui também a uma loja NOS ver se conseguia resolver o problema e disseram-me que o podiam mandar para a garantia mas que não ia valer a pena que vinha igual de lá, porque o único que podiam fazer era formata-lo. O meu equipamento é um Samsung Galaxy Grand Prime e tem 1 ano e 8 meses.
Se alguém souber algo que me possa ajudar, por favor, que me diga.
Obrigado pela atenção,