Yes, because multiple SMTP servers could be used with the EMS edition of Kentico only. What kind of SMTP service are you using?
Also, when you are testing this, could you please confirm that there are no emails in the email queue before?
And definitely.. I would recommend you to apply the latest hotfix for Kentico 7, there were some related bugs fixed. Do you also consider upgrading to the latest version of Kentico? Email provider was improved, so it could also help.
Regards, Martin Danko