IMS Slow to start

I have an exchange server that is purely dedicated to routing internet mail, it had no mailboxes or public folders on it. The problem is that the Internet mail service takes approx 10-15 minutes to start after a reboot of the server.
The box has been rebuilt but to no avail,
does anyone have any suggestions??

Many thanks

Ellen