Emails being rejected by greylisting process when sending emails on behalf of other company

We often send out emails on behalf of other companies (using a modified email header) and recently we have had bouncebacks -

450 4.1.7 : Sender address rejected: unverified address: connect to domain.com[xxx.xxx.xxx.xxx]: Connection timed out

450 4.7.1 : Recipient address rejected: Greylisting in progress

We think that we may need to get the client to add an SPF record with our details so we can send on behalf of them, but we have not had issues like this beforeStart Free Trial