You're most likely not authorized to send e-mail from that system for the domain you're trying to use in the 'From' address per SPF. The webserver should use the domain's authorized mail server as a smart relay.
A lot of systems don't give useful error messages when they think you're a spammer, as it just tells the spammer what they need to fix to get their e-mails through.
There's a chance that the emails that look like they're going through are really being delivered to the recipients' spam folders, and the random fails are to give you a warning so in case it's something done in error you have a warning to correct the problem.
(and this would likely have been better to ask at Server Fault, being an SMTP question; I haven't had to administer an SMTP server in 9 years, so I know of SPF, but I've never had to deal with the issue that it causes)