This resolved the NAT issue(s) for my install too. No more high CPU on my ThinkPad x280 as well.
Thank you @Flawinne_F

This is really discouraging. I am facing the same issue. NAT is no longer working. Cannot ping the NAT gateway. If I go bridged is partially works. My VMs are can acess the internet but I can only ping the gateway using IPV6. This really stinks.

I agree. ALL 16 of my VMs are offline unless I go bridged. Even bridged, IPV4 is not working only IPV6. 

Try the workaround @Flawinne_F suggested

I have not had any other NAT related issues after trying that.