Do you have any access to the mail server logs, or the headers in the messages that have issues?

Beyond SPF, do you also have DKIM setup?

Have you checked your domain and your customers domain against any of the spam blacklist services?

I'm slowly plotting out my own mail server migration soon, and will likely look to research and implement DMARC when the time comes. Currently I have no experience with it, but see it rising up in importance.