You should be at SP4 with the post SP4 hot-fix. There are a number of more recent patches, too. The best thing to do is go to support.microsoft.com (go to the advanced search page) and search for hot-fixes.
The IMC should not take long to start, though it may occasionally take a few minutes to stop (it wants to process messages in the queue before stopping). It sounds like you have a corrupt message in the queue. After stopping the service, look in the exchsrvr\imcdata\out and \in folders. If you don't think it will cause your users any harm, delete whatever is in these folders. That will cause both your outbound and inbound queues to start empty. If you still have a problem, look in the application and system logs (which you should have looked at already) for any clues.
BTW, if you can find a copy of Exchange Server 5.5 In a Nutshell, buy it. It could help you troubleshoot your server.
When all else fails, READ THE DAMN BOOK!
