The FQDN should be a domain YOU own, not the provider.
This implies Postfix isn’t running (or at least not listening to port 25).
If you see this post, this user had a very similar problem as you using Contabo and preinstalled stuff.
Even if the didn’t install LAMP or Virtualmin, just having Webmin installed before could lead to problems and this is obviously what happened here.