Thanks Mike, you said "depending on your setting it might not go right away" and that's the problem. They are not going right away so I changed the settings in OutLook in the TOOLS->OPTIONS->MAIL SETUP-> and checked the Send Immediately option. Now its works fine.
Unfortunately we will be unable to use this solution as we must be able to make sure the mails go immediately and we can't force our users to change their outlook settings to suit us.