Whenever exim restarts it takes up to 3-5 minutes to start responding on the SMTP port. Why is this?

Something else is hanging onto port 25 and not releasing it. One place to look is /etc/inetd.conf in case for any reason an SMTP stream is configured there.

---