In Magento in der configuratiion gibt es eine Einstellung um Emails ein und aus zu schalten.
Bitte kontrollieren sie diese einstellungen.
Ansonsten bietet das maillog auf dem server mehr infos
Wenn es die aktuelle Magento-Version (1.9.1) ist, kann es mit den Cronjobs zusammenhängen.
E-Mails unter Magento CE 1.9.1
System -> Konfiguration -> System -> Mailversand Einstellungen
wenn der Webserver gleichzeitig der Server ist der die mails versenden soll ist localhost korrekt.
bitte prüfen sie die maillogs auf dem Server
Am besten über SSH.
Haben Sie ein shared Hosting vertrag, oder einen eigenen Server? (oder VPS oä?)
Wenn Sie über ssh eingelogt sind können Sie auch über das mail-commando testen ob Sie eine test-email verschicken können:
vielleicht hilft diese Seite:
http://www.binarytides.com/linux-mail-command-examples/