I have no problem sending e-mail from any account of my corporate mail to other accounts including gmail, outlook, yahoo.<o:p></o:p>

Receiving works good too except from when someone is trying to send me from outlook/hotmail account  (that includes web interface services). Then I get the classic error: smtp 530 5.7.0 must issue a starttls command first.<o:p></o:p>

I have tried to follow several approaches I found on web such as activating/deactivating tls, creating an additional connector on exchange server but with no luck.<o:p></o:p>

Has anyone any idea why this is happening for outlook/hotmail and not the others? Could it be due to the fact that the certificate I use is self-signed? Any pointers or other ideas would be much appreciated.

(My installation is on Exchange Server 2003, on Windows Server 2003. Sorry for posting into Exchange Server 2013 forum I had no other option).

You did have another option, several of them in fact:  http://social.technet.microsoft.com/Forums/en-US/category/exchangeserverlegacy

For TLS to work to an external recipient, they must trust it and they won't trust your self-signed certificate.