Have you verified that access to port 25 from localhost works as expected?
Yes it does
Does openssl s_client -connect mail.skjoldebrand.eu:465 work from remote? From localhost to localhost?
Yup both works.
Do you have a firewall?
It hasn't blocked port 25 before (its on the hosting side)
Does your hosting provider filter your network traffic?
You should really have something in the logs when you try to connect.
I think I need to check with the hosting if things are have changed somewhere (possibly due to their recent problems).
/Martin S
