Stop and Remove sendmail, with apt-get. Find the package with apt-cache search
Start postfix /etc/init.d/postfix start
Check the postconf mydestination value with:
The issue was that mydestination included my hostname. Apparently you cant have sender and destination same.
So set the value, by:
postconf -e "destination=...." (the other values)
Now, on retrying a mail send, it gets received/