diff --git a/src/file/fileindexerconfig.h b/src/file/fileindexerconfig.h
--- a/src/file/fileindexerconfig.h
+++ b/src/file/fileindexerconfig.h
@@ -27,6 +27,7 @@
 #include <kconfig.h>
 
 #include "regexpcache.h"
+#include "storagedevices.h"
 
 namespace Baloo
 {
@@ -164,6 +165,8 @@
       */
     uint maxUncomittedFiles();
 
+    StorageDevices* storageDevices();
+
 public Q_SLOTS:
     /**
      * Reread the config from disk and update the configuration cache.
diff --git a/src/file/fileindexerconfig.cpp b/src/file/fileindexerconfig.cpp
--- a/src/file/fileindexerconfig.cpp
+++ b/src/file/fileindexerconfig.cpp
@@ -313,17 +313,13 @@
         return;
     }
 
-    if (!m_devices) {
-        m_devices = new StorageDevices(this);
-    }
-
     KConfigGroup group = m_config.group("General");
     QStringList includeFoldersPlain = group.readPathEntry("folders", QStringList() << QDir::homePath());
     QStringList excludeFoldersPlain = group.readPathEntry("exclude folders", QStringList());
 
     // Add all removable media and network shares as ignored unless they have
     // been explicitly added in the include list
-    for (const auto& device: m_devices->allMedia()) {
+    for (const auto& device: storageDevices()->allMedia()) {
         const QString mountPath = device.mountPath();
         if (!device.isUsable() && !mountPath.isEmpty()) {
             if (!includeFoldersPlain.contains(mountPath)) {
@@ -397,3 +393,11 @@
     return m_maxUncomittedFiles;
 }
 
+StorageDevices* FileIndexerConfig::storageDevices()
+{
+    if (!m_devices) {
+        m_devices = new StorageDevices(this);
+    }
+
+    return m_devices;
+}
diff --git a/src/file/fileindexscheduler.h b/src/file/fileindexscheduler.h
--- a/src/file/fileindexscheduler.h
+++ b/src/file/fileindexscheduler.h
@@ -80,6 +80,7 @@
     Q_SCRIPTABLE void resume() { setSuspend(false); }
     Q_SCRIPTABLE uint getRemainingTime();
     Q_SCRIPTABLE void checkUnindexedFiles();
+    Q_SCRIPTABLE void purgeDeindexableFiles();
     Q_SCRIPTABLE uint getBatchSize();
 
 private Q_SLOTS:
@@ -106,6 +107,7 @@
     TimeEstimator m_timeEstimator;
 
     bool m_checkUnindexedFiles;
+    bool m_purgeDeindexableFiles;
 };
 
 }
diff --git a/src/file/fileindexscheduler.cpp b/src/file/fileindexscheduler.cpp
--- a/src/file/fileindexscheduler.cpp
+++ b/src/file/fileindexscheduler.cpp
@@ -26,6 +26,7 @@
 #include "filecontentindexer.h"
 #include "filecontentindexerprovider.h"
 #include "unindexedfileindexer.h"
+#include "indexcleaner.h"
 
 #include "fileindexerconfig.h"
 
@@ -135,6 +136,18 @@
         Q_EMIT stateChanged(m_indexerState);
         return;
     }
+
+    if (m_purgeDeindexableFiles) {
+        auto runnable = new IndexCleaner(m_db, m_config);
+        connect(runnable, &IndexCleaner::done, this, &FileIndexScheduler::scheduleIndexing);
+
+        m_threadPool.start(runnable);
+        m_purgeDeindexableFiles = false;
+        m_indexerState = DeindexingFileCheck;
+        Q_EMIT stateChanged(m_indexerState);
+        return;
+    }
+
     m_indexerState = Idle;
     Q_EMIT stateChanged(m_indexerState);
 }
@@ -209,6 +222,12 @@
     scheduleIndexing();
 }
 
+void FileIndexScheduler::purgeDeindexableFiles()
+{
+    m_purgeDeindexableFiles = true;
+    scheduleIndexing();
+}
+
 uint FileIndexScheduler::getBatchSize()
 {
     return m_config->maxUncomittedFiles();
diff --git a/src/file/indexcleaner.cpp b/src/file/indexcleaner.cpp
--- a/src/file/indexcleaner.cpp
+++ b/src/file/indexcleaner.cpp
@@ -19,6 +19,7 @@
 
 #include "indexcleaner.h"
 #include "fileindexerconfig.h"
+#include "storagedevices.h"
 
 #include "database.h"
 #include "transaction.h"
@@ -50,8 +51,9 @@
         }
 
         QString url = tr.documentUrl(id);
+        QFile file(url);
 
-        if (!QFile::exists(url)) {
+        if (!file.exists() && file.symLinkTarget().isEmpty()) {
             qDebug() << "not exists: " << url;
             return true;
         }
@@ -71,9 +73,19 @@
         return false;
     };
 
-    for (const QString& folder : m_config->includeFolders()) {
-        quint64 id = filePathToId(QFile::encodeName(folder));
-        tr.removeRecursively(id, shouldDelete);
+    for (const auto& device: m_config->storageDevices()->allMedia()) {
+        if (!device.isMounted()) {
+            qDebug() << "skipping device:" << device.udi();
+        } else {
+            QString devicePath(device.mountPath() + QLatin1Char('/'));
+
+            for (const QString& folder : m_config->includeFolders()) {
+                if (folder.startsWith(devicePath)) {
+                    quint64 id = filePathToId(QFile::encodeName(folder));
+                    tr.removeRecursively(id, shouldDelete);
+                }
+            }
+        }
     }
     tr.commit();
 
diff --git a/src/file/indexerstate.h b/src/file/indexerstate.h
--- a/src/file/indexerstate.h
+++ b/src/file/indexerstate.h
@@ -34,7 +34,8 @@
         ModifiedFiles,
         XAttrFiles,
         ContentIndexing,
-        UnindexedFileCheck
+        UnindexedFileCheck,
+        DeindexingFileCheck
 };
 
 inline QString stateString(IndexerState state)
@@ -64,6 +65,9 @@
         break;
     case UnindexedFileCheck:
         status = i18n("Checking for unindexed files");
+        break;
+    case DeindexingFileCheck:
+        status = i18n("Checking for deindexable files");
     }
     return status;
 }
diff --git a/src/tools/balooctl/main.cpp b/src/tools/balooctl/main.cpp
--- a/src/tools/balooctl/main.cpp
+++ b/src/tools/balooctl/main.cpp
@@ -82,7 +82,7 @@
     parser.addPositionalArgument(QStringLiteral("restart"), i18n("Restart the file indexer"));
     parser.addPositionalArgument(QStringLiteral("suspend"), i18n("Suspend the file indexer"));
     parser.addPositionalArgument(QStringLiteral("resume"), i18n("Resume the file indexer"));
-    parser.addPositionalArgument(QStringLiteral("check"), i18n("Check for any unindexed files and index them"));
+    parser.addPositionalArgument(QStringLiteral("check"), i18n("Check for changes in the monitored folders"));
     parser.addPositionalArgument(QStringLiteral("index"), i18n("Index the specified files"));
     parser.addPositionalArgument(QStringLiteral("clear"), i18n("Forget the specified files"));
     parser.addPositionalArgument(QStringLiteral("config"), i18n("Modify the Baloo configuration"));
@@ -192,8 +192,9 @@
     }
 
     if (command == QStringLiteral("check")) {
+        schedulerinterface.purgeDeindexableFiles();
         schedulerinterface.checkUnindexedFiles();
-        out << "Started search for unindexed files\n";
+        out << "Started search for changes in monitored folders\n";
         return 0;
     }