The solution that seems to keep the service/notification running is to use a repeating alarm:
public void startAlarm(){
alarmMgr = (AlarmManager)this.getSystemService(Context.ALARM_SERVICE);
Intent intent = new Intent(this, NotificationService.class);
alarmIntent = PendingIntent.getService(this, 0, intent, PendingIntent.FLAG_UPDATE_CURRENT);
alarmMgr.setRepeating(AlarmManager.ELAPSED_REALTIME, SystemClock.elapsedRealtime(), 200*1000, alarmIntent);
}
I am not certain of the optimum frequency for resetting the alarm, but I have set it to a few minutes for now. Every few minutes my service is started/resumed.