En esos estados la APP consulta los mensajes en el servidor cada 15 minutos.
Puede ser que por mecanismos propios de cada teléfono, la primera notificación aparezca fuera del rango de esos 15 minutos.
¿En qué teléfono y versión de Android están probando?
Por favor prueben enviar un mensaje y esperar unos 30 minutos a ver si aparece la notificación.