For anyone unsuccesfully searching for answers - and coming to this topic:
I just had the pleasure of figuring out my VPS hosting provider, requires me to enable the outgoing mailports first, on a freshly installed box. I knew this, but only remembered after a nights sleep 
Happy Hosting! 