Thanks Samuel,
I got in touch with my host, they claim eigbox.net to be their email server. They are in their world of denial. As per them eigbox.net is not blacklisted anywhere.
I tried changing the php.ini file, setting values to other smtp servers, doesnt have any effect. I still get ‘via eigbox.net’.
Is it possible to do some little tinkering with relevant WP file or functions.php to force WP to use my smtp for sending out these mails. And how?
As I said earlier, I would like to avoid yet another plugin.