Exchange 5.5 Internet Mail Service

Recently our internet mail service stopped working (thus making our custom recipients not able to receive mail) When you try to restart the service it is a no go. It times out and will not respond. I have tried removing and reinstalling the service but no jive. SP3 was recently installed, but these problems occoured right before SP3 was installed… Any ideas?
Thx