mis contactos almacenados que tienen el código de país añadido NO se corresponden con los contactos de llamada existentes

Si quieres una respuesta rápida (dos en realidad) esto es lo que yo haría:

1) Ve a Ajustes > Cuentas > elimina la cuenta de Google > vuelve a añadirla.
Lo probé una vez y funcionó...
2) Ve a Gmail en un ordenador de sobremesa > Ve a Configuración (el icono del engranaje en la parte superior derecha) > En General, ve a "Números de teléfono" y selecciona tu código de país predeterminado en la lista desplegable.
De este modo, tu dispositivo debería reconocer automáticamente las llamadas entrantes de tu país...

No estoy seguro de que uno de estos sea la solución a tu problema, pero sé que mucha gente resolvió el mismo problema usándolos. Prueba y dime si funcionan. Si no, buscaremos otra solución ;)

Sé que esta no es una solución perfecta, pero es sólo una solución alternativa. Truecaller aplicación. Sin embargo, esto requiere una conexión a Internet activa durante el tiempo de recepción de la llamada.