Mail sitting in "message pending submission" queue for 6-8 minutes

I have got an SBS 2003 setup that is running Exchange 2003. Everything has been working fine untill last couple of days. I have installed ISA server from the Premium Tools then realised that it would be more prudent to install this in a VM / Test environment, so I uninstalled ISA. The issue that I am facing now is when email is processed, whether it is external or internal, it sits in the "message pending submission" queue for about 6 minutes and then delivers normally. When I turned on message tracking then I can see that the pause is between:

10.00 SMTP; Message submitted to advanced queuing
10.06 SMTP; Started message submission to advanced queuing

I dont have any antivirus application on the server as this is handled by a barracuda spam filter. Is there anyone who can share some idea to fix this issue? Thanks.

It is recommend that you set up Windows SBS by using the Configure E-mail and Internet Connection Wizard (CEICW). You may have to manually set up some settings in scenarios that aren't supported by the wizard. For more information visit this website - http://support.microsoft.com/?id=825763

If you want to resolve this problem then try to remove the _msdcs zone and subfolder and then re-registed this information and then check if the problem persists. Also take the backup of your server before following the below steps:

1. First of all open DNS management console.
2. After that try to expand "Forward Lookup Zones".
3. Now you have to check if the _msdcs.domain.local zone exists. If so, delete it.
4. After that you need to check if the _msdcs subfolder exists under the domain.local zone. If so, delete it.
5. Now try to open Services console from Administrative Tools.
6. After that you need to stop Net Logon service and then restart this service. (This will recreate the zones and subfolders required for AD)
7. Now you have to run the following command under Command Prompt.