¿Cómo puede WhatsApp recibir mensajes cuando no está en uso?

¿Cómo podría el servidor hacer un push? Esa es la clave de la pregunta.

He actualizado mi respuesta para incluir una posibilidad de cómo el servidor podría lograr un push.

Gracias por ser más específico, pero sigo pensando que el quid de la cuestión no fue examinado en tu análisis. El paso 8 es el problemático para mí: ¿cómo "envía el mensaje a tu teléfono"? ¿Envía un paquete de red? Pero, ¿cómo puede tu dispositivo recibir un paquete de red sin estar continuamente conectado? ¿O tal vez hay algún tipo de mecanismo con el que no estoy familiarizado que hace que la conexión se restablezca cuando se envía un paquete de red a tu teléfono?

Permítanme tratar de explicar un poco más: Hay un recurso que se está utilizando continuamente. Es el socket de escucha que fue abierto por el servicio de WhatsApp. Simplemente se queda allí en su teléfono esperando una conexión de red entrante (ver listen(2) para más información). Esto no tiene prácticamente ningún costo en memoria, batería u cualquier otra cosa. Cuando el servicio de WhatsApp se registra con el servidor, envía la información suficiente para que el servidor establezca una conexión de red con el socket de escucha (llamando a connect(2)).

Cuando dices "esperando una conexión de red entrante", ¿te refieres a esperar a que se establezca una conexión TCP? ¿Cómo puede esperar algo así cuando el teléfono no está conectado a Internet? ¿O hay algún tipo de mecanismo que conecta el teléfono a Internet cuando hay un mensaje de Whatsapp para recibir?

Sí, esperando una conexión TCP. Mientras no haya apagado explícitamente el WiFi y los datos móviles, su teléfono está conectado a Internet, incluso si la pantalla está apagada.

Nat no permitirá el paso 8, incluso si el móvil tiene una IP estática, lo cual nunca será el caso. Las posibles formas son Xmpp o polling largo http.

Tiene el permiso requerido. Está listado como "recibir datos de Internet" en la Play Store. Ver android.stackexchange.com/a/61794

Lamentablemente, las conexiones TCP entrantes son casi imposibles en dispositivos móviles. La abrumadora mayoría de ellos no tienen direcciones IP públicas, e incluso si las tienen (por ejemplo, para operadores capaces de IPv6), las conexiones entrantes suelen estar filtradas. La mayoría de las aplicaciones hoy en día utilizan los servicios de envío de Google o crean su propio cliente persistente de conexión de socket al servidor (sobre todo Facebook). WhatsApp parece seguir un enfoque híbrido, en mi experiencia: si GCM está disponible, el socket persistente se cierra después de estar inactivo durante unos minutos.