webservice en .NET + JSON + Android es rapidisimo te lo digo por experiencia, trae miles de datos en segundos, y si esto es solo un mensaje como un simple string pues no tardaria casi nada en traerlo, eso si tendrias que consultar la base de datos.
ahora ya si queres hacer algo como push es otra cosa,
Google Cloud Messaging for Android (GCM) Google Cloud Messaging for Android