Вам нужно будет использовать BroadcastReciever для прослушивания намерения "android.provider.Telephony.SMS_RECEIVED". На этой странице есть хороший пример того, как его настроить.
Редактировать: Я не думаю (но я не совсем уверен), есть ли способ получить уведомление, когдасообщение собирается быть удаленным.Почему вашему приложению необходим доступ к удаляемым ими SMS-сообщениям пользователя?