TL;DR: There's only one change due to March Patchday: KB3139852 replaces KB3134214.

Valid as of: Mar 2016 (2016-03-09)
Valid until (presumably): Apr 2016 (2016-04-12)

Solution to the issue

There are at least four updates which have to be installed on a newly installed Win7 SP1 or Vista SP2 BEFORE letting Windows search for updates, to avoid this very search taking "forever":

KB	Win7 x64	Win7 x86	Vista x64	Vista x86
KB3139852	Download	Download	Download	Download
KB3078601, "loyal" companion since August 2015	Download	Download	Download	Download
KB3087039	Download	Download	Download	Download
KB3109094	Download	Download	Download	Download

To reduce memory and CPU usage while searching for updates, one should install the following updates as well:

Windows Update Client:
KB3075851 August 2015, or one of its successors

KB3083324	September 2015
KB3083710	October 2015
KB3112343	December 2015
KB3134554	February 2016
KB3138612	March 2016

Every one of them reduces the Update Agent's memory usage (having a good effect, especially on systems with less RAM).

The following update is (most likely) not required if the Windows Update Client of December 2015 or later is already installed:
KB3102810, reduces Update Agent's CPU load.

Steps to take after Windows installation

Disable Automatic Updates:
Start > Control Panel > System and Security > Windows Update > Change settings > "Never check for updates"
(Optional) Stop "Windows Update" service: Open Windows Task Manager > Tab "Services" > Right-click on "wuauserv" > Stop service
Download the updates mentioned above and install them via WUSA on a CMD shell (as Administrator):
```
"%SystemRoot%\system32\wusa.exe" "C:\full\path\to\Update.msu" /quiet /norestart
```
Reboot the system.
Now let Windows search for updates, which should be finished in less than 15 minutes.
Re-enable automatic updates (see step to disable them, but select one of the options to search for updates automatially now), and install the remaining updates as usual.

Note: These instructions were only tested on Win7 SP1. However, the list of updates above should speed up the search for updates on Vista SP2, too.

Thanks to T. Wittrock, author of WSUS Offline Update, Denniss and the community.

Regards
Dalai