Ich verschicke manchmal über 20k Mails am Tag ohne probleme bei maxmal 500 Mails pro User...

Eventuell hat dein Hoster eine begrenzung von ausgehenden Mails?