POP3 and PST search broken by March 2017 Update for Outlook 2016

An issue has surfaced with the March Update for the Current Channel of Outlook 2016 for people that are using an Office 365 installation. After updating to this release or higher, search stops working for POP3 accounts and PST files.

Update:
This issue has been fixed in version 16.0.7870.2031. After applying this update, your Search Index might start to rebuild itself which could result in high(er) CPU usage and incomplete or no search results. Once everything has been indexed again, CPU usage will reduce again.

When you are still encountering Search issue then, continue with the regular troubleshooting steps to get Instant Search working again.

You can check whether your installation is affected by going to; File-> Office Account. When this states that you are using Version 1702 (Build 7870.2020) or later, then your build is affected.

When you are indeed using a POP3 account and/or pst-files and search is no longer working for you, the current workaround is to revert to build 16.0.7571.2109 which is the January 4 release, also being referred to as Version 1611. Microsoft is actively investigating this issue but no release date for a fix could be provided at this point.

Uninstalling the update

Before uninstalling the update, disable automatic update via:
File-> Office Account-> Update Options-> Disable Updates

Additionally, create a reminder in your Calendar to re-enable updates in May as a fix for this issue should be deployed by then (possibly even in April).

To uninstall the update and revert to Version 1611, open a Command Prompt as an Administrator and run the following command:

"C:\Program Files\Common Files\Microsoft Shared\ClickToRun\OfficeC2RClient.exe" /update user updatetoversion=16.0.7571.2109

For more details and screenshots see: Uninstall Office 365 Click-To-Run Updates.