Search is broken on Windows 2008 R2

Question

The ability to search for anything on one of my Windows 2008 R2 servers has, for reasons unknown, stopped working.

For example I can't search for anything via the Start Menu:

Clicking "See more results" displays this error dialogue:

I can't search for files or folders in Explorer (there's no network drives, just a C: drive). All that happens is the search term is displayed in the explorer window title bar (see red highlights):

And most annoyingly, I also can't search for specific installed updates. Again all that happens is the search term is repeated in the window title bar:

This isn't because the Windows Search feature isn't installed. My other Windows 2008 R2 servers don't have that installed either but their search widgets work just fine.

I did bump into this hotfix:

The "Search programs and files" box does not display search results correctly in Windows 7 and in Windows 2008 R2 (KB977380)

But when I try to install it I'm told that:

The update is not applicable to your computer.

I also tried the workaround in this article which involves deleting the following HKEY_CURRENT_USER registry key:

HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\FolderType‌​s\{ef87b4cb-f2ce-4785-8658-4ca6c63e38c6}

I also tried creating different accounts on this server as well and all result in the same behaviour described above.

Finally, I also tried the solution provided in the answer to this question but that didn't work either:

Windows 7's start menu's search "see more results" is broken

I don't need to search for matching expressions inside files, I just need to search for files and folders names matching a pattern, stuff on the start menu and in particular for specific Windows Updates and hotfixes.

How do I get search working again on this server?