Suele suceder cuando el que recibe tiene un modelo de teléfono obsoleto o muy antiguo.
A mí me pasaba con un amigo que tiene un Samsung modelo "concha", de hace unos 6 años.
Lo solucioné instalando
Handcent y ahora los que le envío a él con esa app le llegan bien.
Con contactos que tienen un smartphone no me pasó nunca.