A method implemented in a notification service, the method comprising: receiving at the notification service, from an application service, a message targeting one of multiple applications on a computing device, wherein the notification service and the application service are each implemented on different computing devices that are each separate from the computing device; maintaining at the notification service in an application status store information that identifies statuses for the multiple applications on the computing device, based at least in part on previously received indications from the computing device, wherein the information identifying the statuses for the multiple applications on the computing device is deleted from the application status store each time the computing device disconnects from the notification service, wherein at least one of the previously received indications comprises an indication, received from the computing device, to block notifications for a particular application, the previously received indication having been received in response to the application not running on the computing device and the application not being permitted to run as a background application on the computing device; determining, based at least in part on a status for one of the multiple applications, whether notifications for the application on the computing device are blocked; and providing from the notification service, to the computing device, a notification targeting the application and including data from the message only in response to determining that notifications for the application on the computing device are not blocked. receiving at the notification service, from an application service, a message targeting one of multiple applications on a computing device, wherein the notification service and the application service are each implemented on different computing devices that are each separate from the computing device; maintaining at the notification service in an application status store information that identifies statuses for the multiple applications on the computing device, based at least in part on previously received indications from the computing device, wherein the information identifying the statuses for the multiple applications on the computing device is deleted from the application status store each time the computing device disconnects from the notification service, wherein at least one of the previously received indications comprises an indication, received from the computing device, to block notifications for a particular application, the previously received indication having been received in response to the application not running on the computing device and the application not being permitted to run as a background application on the computing device; determining, based at least in part on a status for one of the multiple applications, whether notifications for the application on the computing device are blocked; and providing from the notification service, to the computing device, a notification targeting the application and including data from the message only in response to determining that notifications for the application on the computing device are not blocked.