I opened the Services MMC snap-in and saw that the following services were disabled:
- Function Discovery Resource Publication _ set it o Automatic and start it.
- SSDP Discovery
- UPnP Device Host
Enabling and starting these services did the trick and now Network Discovery is enabled and I can see the server. It doesn't explain why toggling this in the UI didn't enable these services.