Who do you have your SMTP agent setup through? If you're using SendGrid or another agent, some of them may hold those emails until you verify the activity is valid.
For instance, had a SendGrid account for one of my clients for 3 years but only sent 5-10 emails through it every month. We started using email campaigns in Kentico and sent out a campaign with 36,000 emails in it and SendGrid held them all until we verified the activity was valid.