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:

postconf -n

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/