In case you can't connect to your local SMTP server, for example from Perl's Mail::Sendmail, make sure to check the following:
It might be that localhost and the IP address Exim is listening on are not the same! Do this:
$ netstat -anp | grep " LISTEN "
This will output all the ports local services are listening on. When Exim is running, it should be listed, and also, the IP address it is listening on. Chances are good, the listed IP is not the one you were expecting.
Now, do a reconfigure of Exim, on Debian that is done with:
$ dpkg-reconfigure exim4-config
And when it comes to "enter IP adresses Exim should listen on" be sure to add "127.0.0.1". After that, even the Perl module Mail::Sendmail should work without any tweaks.