diff --git a/java/com/android/dialer/app/calllog/CallLogNotificationsQueryHelper.java b/java/com/android/dialer/app/calllog/CallLogNotificationsQueryHelper.java
index 4745736..3a4bf87 100644
--- a/java/com/android/dialer/app/calllog/CallLogNotificationsQueryHelper.java
+++ b/java/com/android/dialer/app/calllog/CallLogNotificationsQueryHelper.java
@@ -26,6 +26,7 @@
 import android.net.Uri;
 import android.os.Build;
 import android.provider.CallLog.Calls;
+import android.provider.VoicemailContract.Voicemails;
 import android.support.annotation.NonNull;
 import android.support.annotation.Nullable;
 import android.support.annotation.VisibleForTesting;
@@ -365,6 +366,11 @@
               .and(Selection.column(Calls.NEW).is("= 1"))
               .and(Selection.column(Calls.TYPE).is("=", type))
               .and(Selection.column(Calls.IS_READ).is("IS NOT 1"));
+
+      if (type == Calls.VOICEMAIL_TYPE) {
+        selectionBuilder.and(Selection.column(Voicemails.DELETED).is(" = 0"));
+      }
+
       if (thresholdMillis != NO_THRESHOLD) {
         selectionBuilder =
             selectionBuilder.and(
diff --git a/java/com/android/dialer/app/calllog/VisualVoicemailUpdateTask.java b/java/com/android/dialer/app/calllog/VisualVoicemailUpdateTask.java
index e3279ce..2e12cec 100644
--- a/java/com/android/dialer/app/calllog/VisualVoicemailUpdateTask.java
+++ b/java/com/android/dialer/app/calllog/VisualVoicemailUpdateTask.java
@@ -67,9 +67,11 @@
       // Query failed, just return
       return;
     }
-    boolean shouldAlert = !voicemailsToNotify.isEmpty();
-    voicemailsToNotify.addAll(getAndUpdateVoicemailsWithExistingNotification(context, queryHelper));
     voicemailsToNotify = filterBlockedNumbers(context, queryHandler, voicemailsToNotify);
+    boolean shouldAlert =
+        !voicemailsToNotify.isEmpty()
+            && voicemailsToNotify.size() > getExistingNotificationCount(context);
+    voicemailsToNotify.addAll(getAndUpdateVoicemailsWithExistingNotification(context, queryHelper));
     if (voicemailsToNotify.isEmpty()) {
       LogUtil.i("VisualVoicemailUpdateTask.updateNotification", "no voicemails to notify about");
       VisualVoicemailNotifier.cancelAllVoicemailNotifications(context);
@@ -107,6 +109,25 @@
     VoicemailNotificationJobService.scheduleJob(context);
   }
 
+  @WorkerThread
+  @NonNull
+  private static int getExistingNotificationCount(Context context) {
+    Assert.isWorkerThread();
+    int result = 0;
+    for (StatusBarNotification notification :
+        DialerNotificationManager.getActiveNotifications(context)) {
+      if (notification.getId() != VisualVoicemailNotifier.NOTIFICATION_ID) {
+        continue;
+      }
+      if (TextUtils.isEmpty(notification.getTag())
+          || !notification.getTag().startsWith(VisualVoicemailNotifier.NOTIFICATION_TAG_PREFIX)) {
+        continue;
+      }
+      result++;
+    }
+    return result;
+  }
+
   /**
    * Cancel notification for voicemail that is already deleted. Returns a list of voicemails that
    * already has notifications posted and should be updated.