As answered on https://github.com/FusionAuth/fusionauth-issues/issues/1263, this was indeed an issue with port 25.
For anybody encountering the same problem:
- Try switching to another port (587, 465, or 2525)
- Try switching TLS to SSL and the other way around with all the different port configurations.
Took me a while to find this, probably because I mistyped 587 as