Cuando se elimina una aplicación de la Play Store, ¿se elimina del teléfono de todos los que la han descargado?

En general, la respuesta es no - sin embargo, Google tiene la capacidad de eliminar remotamente las aplicaciones (es decir, el malware) del dispositivo de todo el mundo, según sea necesario, y si lo hacen le proporcionará una notificación.

Esto fue explicado por Rich Cannings, jefe de seguridad de Android en una entrada del blog de Android Developers, allá por 2010:-

... En los casos en que los usuarios puedan haber instalado una aplicación maliciosa que suponga una amenaza, también hemos desarrollado tecnologías y procesos para eliminar de forma remota una aplicación instalada en los dispositivos. Si una aplicación se elimina de este modo, los usuarios recibirán una notificación en su teléfono.

Recientemente, tuvimos conocimiento de dos aplicaciones gratuitas creadas por un investigador de seguridad con fines de investigación ... Después de que el investigador retirara voluntariamente estas aplicaciones de Android Market, decidimos, de acuerdo con las condiciones de servicio de Android Market, ejercer nuestra función de eliminación remota de aplicaciones en las copias instaladas restantes para completar la limpieza.

... una aplicación peligrosa podría ser retirada de la circulación activa de una manera rápida y escalable para evitar una mayor exposición a los usuarios. Aunque esperamos no tener que usarla, sabemos que tenemos la capacidad de tomar medidas rápidas en nombre de la seguridad de los usuarios cuando sea necesario. ...

Esto se utilizó para eliminar 60 maliciosos aplicaciones en 2011

El martes por la noche, el equipo de Android tuvo conocimiento de una serie de aplicaciones maliciosas publicadas en Android Market. A los pocos minutos de tener conocimiento, identificamos y eliminamos las aplicaciones maliciosas. ... Sin embargo, dada la naturaleza de los exploits, el atacante o atacantes podrían acceder a otros datos, por lo que hemos tomado una serie de medidas para proteger a quienes descarguen una aplicación maliciosa:

Hemos eliminado las aplicaciones maliciosas de Android Market, hemos suspendido las cuentas de los desarrolladores asociados y nos hemos puesto en contacto con las fuerzas del orden para informarles del ataque. Estamos eliminando remotamente las aplicaciones maliciosas de los dispositivos afectados. Esta función de eliminación remota de aplicaciones es uno de los muchos controles de seguridad que el equipo de Android puede utilizar para ayudar a proteger a los usuarios de las aplicaciones maliciosas. ...

Aunque no es exactamente una respuesta a tu pregunta, hace poco vi que esto ocurría, y la causa era que un desarrollador de aplicaciones había cambiado el nombre de la aplicación. Cuando se hizo una actualización automática, la antigua aplicación desapareció y se instaló la nueva. Pero, el icono fue eliminado de mi página del lanzador, y el nuevo no se puso allí. Una vez que me di cuenta de por qué tenía un lugar vacío, y cuál era el nuevo nombre, fui capaz de ponerlo de nuevo.
A mí me confundió un poco, y pudo ser lo que te pasó a ti. No sé por qué una actualización consideraría que las dos aplicaciones son la misma, pero el lanzador no, pero eso es lo que pasó.

No, no es así. De hecho, uso varias aplicaciones que han sido eliminadas de la Play Store desde que las instalé.