How can I get Windows Server 2016 start menu search to work, fully?

The issue is discussed on this Microsoft support page. Basically you just need to enable the Windows Search service:

1. Press the Windows key‌ + R to open the Run box.
2. Type services.msc, and then press Enter.
3. Right-click Windows Search, and then click Properties.
4. Change the Startup type to Automatic (Delayed Start).
5. Click Apply, and then click Start.
6. Click OK, and then close the Services console.

It may take a while for it to index everything and make it available to be found by the search.

We had the same problem with our Windows Server 2016 Standard installation. We could fix it by following this guide. Don't be confused that it addresses another problem. You can test if this will work for you, if you open the startmenu and run "Cortana & Search Settings" (just type "search", it will be found, even with the broken startmenu). If it shows

Search can't be opened using the Built-In Administrator account. Sign in with a different account and try again.

then the solution in the guide will work.

For future references if the guide gets unavailable:

1. Run gpedit.msc
2. Go to Computer Configuration > Windows Settings > Security Settings > Local Policies > Security Options
3. Enable the policy User Account Control: Admin Approval Mode for the Built-in Administrator Account
4. Restart the server. Signing out and logging in again doesn't suffice.

Be aware, that this solution has the downside of half-enabling UAC again for the built-in administrator. As long as EnableLUA is deactivated, it should not annoy you, but I am not experienced enough to tell if it has any other major side effects.