La única solución que se me ha ocurrido es tener un servidor...
Movil envía información al servidor mediante udp, servicio web...
Servidor envía mediante C2DM ( notificaciones push ) al otro movil
Con todo lo que llevo buscando, cada vez le doy más importancia al whatsapp...
Salu2!!