I'm writing this because I found ~10 articles on Google with a similar question and I didn't feel like signing up for 10 accounts just to help someone out.
The issue: My Windows Server 2016 guest machine suddenly couldn't recognize the network connection.
I logged in and also saw that it was running some patches - so obviously the network connection worked while downloading the patches. I assume that part of the forced "security update" rampage that Microsoft is on caused the driver to get unloaded. I tried reconnecting the adapter in VirtualBox but it didn't work. NAT networking was fine, but I couldn't get the Bridged Adapter to work. I used the Bridged adapter because I have a very special network setup (because I'm behind the GFW of China) and I need to have static IPs on my guest OSes.
The solution: Switch the network adapter type to "Intel PRO/1000 MT Server"
Found here. By default, VirtualBox uses the Desktop version. Also, I noticed that after I connected a new adapter with the "Server" type, the original "Desktop" adapter suddenly started working. I assume Windows grabbed a different driver for the Server version and then re-used this for the Desktop version.