А чем простой Service плох? Сейчас так делаю : при запуске проверяю есть ли объект AlarmManager, если есть - значит сервис уже работает. Иначе создаю его, получаю список уведомлений из базы данных и на их основании делаю нотификации примерно таким образом :

Intent intent = new Intent(this, NotifyActivity.class);
            PendingIntent ai = PendingIntent.getActivity(this, 0, intent, 0);

            Calendar calendar = Calendar.getInstance();
            calendar.setTimeInMillis(System.currentTimeMillis());
            calendar.set(Calendar.HOUR_OF_DAY, 12);
            calendar.set(Calendar.MINUTE, 37);

            this.alarmManager.setRepeating(AlarmManager.RTC_WAKEUP, calendar.getTimeInMillis(),
                    AlarmManager.INTERVAL_DAY, ai);

На месте цифр 12 и 37 естественно получение часов и минут из модели данных. PendingIntent'ы храню в массиве там же в сервисе чтобы иметь возможность отменить нотификацию(и).

У первой задачи сервис убрал в один процесс с основным приложением. Посмотрю как отработает.

Блин после десктопной явы андроид это какой-то филиал ада. Я в свое время писал демонов, которые на машинах с хрюшей на борту умудрялись иметь аптайм по несколько месяцев подряд. А тут выходит что что угодно может быть прибито когда угодно, все в воле левой пятки ОС