Tuve exactamente el mismo problema. Mi Mac, iPhone o iPad no se conectan porque el icono desaparece a intervalos aleatorios.
Puedes intentar conectar un cable Ethernet, sin embargo esto no parece solucionar el problema de forma permanente.
Lo que hice fue obtener un nuevo enrutador que admite banda dual (2.4 GHz y 5 GHz). El iPhone usa 2.4 GHz y mi Mac y AppleTV usan 5 GHz. Había menos tráfico de esa manera (debido a la división de las bandas en diferentes dispositivos) a través del enrutador y el AppleTV siempre se detecta. Esto obligó a que la opción AirPlay apareciera siempre en mis dispositivos.
Puede consultar mi pregunta y otras posibles respuestas aquí ¿Desapareció la opción AirPlay?