Hombre, en teoría un servicio no es más que un programa normal y corriente, pero sin acceso a la interfaz gráfica. En Windows, por ejemplo, puedes hacer correr cualquier programa normal como servicio; hay diferencias en cuanto a tema de permisos y tal, pero hacen la misma función y consumiendo en teoría los mismos ciclos de procesador. En Android, por lo que he visto, la diferencia es sobre todo a la hora de decidir Android que programas cierra, pero el consumo de procesador (y por tanto de batería) no tiene porqué ser diferente.
En cuanto al otro tema, push simplemente significa que es el servidor el que "empuja" las datos al cliente, a diferencia del pull donde es el cliente el que hace comprobaciones periódicas. Por tanto, todos los MSN siempre serán push, si fuera pull te llegarían los mensajes a los segundos o minutos en vez de instantáneamente. Y por eso el MSN necesita estar conectado contínuamente, si fuera pull no le haría falta.
Si no hay "ningún servicio de ninguna aplicación concreta" corriendo.. ¿entonces cuál es proceso que recoge el mensaje del servidor? Si no hay una conexión abierta.. ¿cómo se las apaña el servidor para ponerse en contacto con el cliente? (las conexiones las tiene que establecer siempre el cliente, el servidor no puede).