Si, a mi me ocurre lo que comentas, y desde hace bastante tiempo (como mínimo, año y medio) tanto en Movistar directo como en O2. Tiene pinta por lo que he podido observar de ser algún bug a la hora de conectar al IMS (aunque VoLTE si funciona). El problema a mi se me reproduce tanto con terminales Samsung como Oppo y Xiaomi.
La "solución" que yo tengo más efectiva cuando esto ocurre, es desactivar la conectividad WiFi del teléfono y volverla a activar. A veces, con esto es suficiente, pero otras no, y tengo que dar un paso adicional poniendo modo avión o reiniciando el teléfono, y entonces ya se conecta correctamente a VoWiFi. Prueba esto cuando te ocurra.
Evidentemente cuando he expuesto este asunto en el 1551 y 1004, parecía que les hablaba en chino, por lo que dudo que alguien pueda dar con una solución al problema, al menos en corto plazo.
Con el VoWiFi de Orange en cambio no ocurre, conexión siempre a la primera aunque salgas y entres de casa 20 veces.