PHPBB Registration Mail fails with error

Registration mails are not getting sent, though I can mass e-mail from the ACP with no problems.

New registrations generate an error from Anonymous in the PHPBB error log:

E-mail error

» EMAIL/PHP/mail()

Relevant settings in ACP:

Account activation: By User
Enable board-wide e-mails: Enabled
Users send e-mail via board: Enabled
E-mail function name: mail
Contact e-mail address:
Return e-mail address:
Use SMTP server for e-mail: No
Newly Registered Users permission for Send Emails: yes