First off, running Exchange on your PDC is a big No-No! It is highly advisable that you get a dedicated server for Exchange.You will save yourself a lot of aggravations in the long run!
As for the IMS queue issue, how long has this problem existed? Is this a new install or one that has been working correctly up until recent? Have you made any changes to your server since the last time your IMS worked correctly? Do you experience problems sending messages to local recipients or just with Internet mail? Any trouble recieving messages from the outside? After restarting the IMS and clearing the queue, have you confirmed that mail is getting to it’s destination? Maybe send a test message to an Internet mail account (AOL, Hotmail etc.)to confirm your mail is getting to it’s destination.
Though rare, I have heard of anti-virus software causing very similar problems as your describing. If you are using anti-virus on this server, check your software settings to confirm that nothing is blocking outbound traffic on port 25. Otherwise, you may want to confirm config settings for your SMTP and IMAP services as there may be something that you have overlooked. Wouldn’t hurt to check your POP3 services as well though POP3 is really for receiving Internet mail and not sending. Probably wouldn’t hurt to check your DNS and firewall settings as well.
This should get you started. If the problem still persists, update your question to include better detail of what exactly is happening as well as any actions you have already taken. The more info you can provide, the better your chances are of getting help!