Here is an update.
I rebuilt the DigitalOcean droplet to a fresh Ubuntu 16 install.
Installed Softether. Tried to connect to it but my router and even PC kept throwing authentication error messages.
Enabled SecureNAT. Both devices connected immediately.
Tried the Xbox One. It shows Strict, but everything is working perfectly fine and Forza Horizon 3 is super fast! Didn’t try Party Chat yet as none of my friends are online in the mean time.
I thought Microsoft had the IP of the droplet blocked but apparently it was bad configuration on the normal OpenVPN.
I also tried to use PPTP and L2TP but of course my ISP has them blocked.