diff --git a/AndroidManifest.xml b/AndroidManifest.xml
index 861fd1d..638c2c4 100644
--- a/AndroidManifest.xml
+++ b/AndroidManifest.xml
@@ -49,6 +49,7 @@
     <uses-permission android:name="com.android.launcher.permission.INSTALL_SHORTCUT"/>
     <uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED" />
     <uses-permission android:name="android.permission.BROADCAST_STICKY" />
+    <uses-permission android:name="android.permission.ACCESS_WIFI_STATE" />
     <!-- This tells the activity manager to not delay any of our activity
      start requests, even if they happen immediately after the user
      presses home. -->
diff --git a/src/com/android/dialer/calllog/CallLogQueryHandler.java b/src/com/android/dialer/calllog/CallLogQueryHandler.java
index dfc9c78..761c8e0 100644
--- a/src/com/android/dialer/calllog/CallLogQueryHandler.java
+++ b/src/com/android/dialer/calllog/CallLogQueryHandler.java
@@ -32,11 +32,13 @@
 import android.os.Message;
 import android.provider.CallLog.Calls;
 import android.provider.VoicemailContract.Status;
+import android.provider.VoicemailContract.Voicemails;
 import android.util.Log;
 
 import com.android.common.io.MoreCloseables;
 import com.android.contacts.common.database.NoNullCursorAsyncQueryHandler;
 import com.android.dialer.voicemail.VoicemailStatusHelperImpl;
+
 import com.google.common.collect.Lists;
 
 import java.lang.ref.WeakReference;
@@ -140,15 +142,18 @@
         StringBuilder where = new StringBuilder();
         List<String> selectionArgs = Lists.newArrayList();
 
+        // Ignore voicemails marked as deleted
+        where.append(Voicemails.DELETED);
+        where.append(" = 0");
+
         if (newOnly) {
+            where.append(" AND ");
             where.append(Calls.NEW);
             where.append(" = 1");
         }
 
         if (callType > CALL_TYPE_ALL) {
-            if (where.length() > 0) {
-                where.append(" AND ");
-            }
+            where.append(" AND ");
             // Add a clause to fetch only items of type voicemail.
             where.append(String.format("(%s = ?)", Calls.TYPE));
             // Add a clause to fetch only items newer than the requested date
@@ -156,9 +161,7 @@
         }
 
         if (newerThan > 0) {
-            if (where.length() > 0) {
-                where.append(" AND ");
-            }
+            where.append(" AND ");
             where.append(String.format("(%s > ?)", Calls.DATE));
             selectionArgs.add(Long.toString(newerThan));
         }