I am looking for a way they can send emails that are from their own addresses – and not from my domain (via sendmail).

These mails should not have a on behalf of in their FROM, but also I want to make sure that my service will not get gamed by spammers.

One idea was that every client can set up her own SMTP settings which Swiftmailer will then use to deliver the mails for each individual address. Maximum daily delivery per client should by below 500, so that might work.

Another idea was to use a service such as Amazon SES, who let you verify up to 1000 addresses (1). Or Sendgrid, who offer something similar.

What is the most secure way to send mails from different addresses with a maximized deliverability and minimum risk of being gamed by spammers?

(1) http://docs.aws.amazon.com/ses/latest/DeveloperGuide/verify-email-addresses.html (2) https://sendgrid.com/docs/Classroom/Send/How_Emails_Are_Sent/can_i_send_from_multiple_from_addresses.html