Hit me up at jack at my domain name (found in my profile. But not hard to guess) with their domain name and I’ll have a look (pref from the domain that needs to be configured so I can see the headers, infact send me one from the domain in question and one from your own email address just incase my own spam filters catch the one from the clients domain name :-P).

Iirc tucows don't “directly” sell and host email to the general public. But offer reseller accounts or they are sold and hosted to the general public by their subsidiary Hover.

So just because its a "tucows domain" doesn't mean its actually tucows hosting your email services, anyways...

You might be able to get away without DKIM if the email is coming from “safe known ips” which hopefully your email provider has told the various big email providers.

SPF can be done completely from a DNS record. Google a SPF generator, fill in the details, and throw the result into your DNS records and done.

DKIM is a bit different as the outgoing mail server signs your outgoing email. The receiving party then check your DNS for the public key for the email.

Your mail provider might already be signing outgoing mail and you just need to put the public key on the DNS or you will need to contact your mail provider and ask them to turn it on for you. (If it’s is hover their customer support has always been good~ish to me. I think I’ve had one issue with them in the past, but it was a minor issue and I still have a few domains reg’ed with them. Anyways back on point.)

You can use something like https://www.appmaildev.com/en/dkim/ to check if you mail is already being signed and get the public key for it.

If your email provider is refusing to set up DKIM for you, you can try with just SPF and hope the reputation of the mail server itself is enough to fill in the blank of DKIM or moved to another provider either self hosted (cheaper, but more manual setup) or something like FastMail which does offer easy to configure DKIM (plus things like iOS Mail Push support) or an SMTP relay (depending on the volume of outgoing mail you might get away with using the free allowance from say sendgrid, sendpulse, mailgun or one of the many others out there.)

Obv trying to get your current provider up and running is the preferred option as then your client and any other mailboxes they have won’t need to chan he any of their mail client settings to get up and running.

EDIT: Also, having DKIM and SPF correctly configured doesn't always matter. Outlook for example may still reject your mail if it comes from an IP that they are not expecting. But you can ask them to add a mitigation for you via https://support.microsoft.com/en-us/supportrequestform/8ad56... (If they reply saying "Nope your not blocked..." just email them back politely asking them to check again as you are still having deliverability issues. I personally had this recently, but it was fixed with a follow up email so I'm not going to complain about it). Though as you are not the outgoing mail provider yourself you may not be able to answer all the questions (Are you sure you know all the ip ranges your mail provider use?). Gmail may get mad at you if you are doing a catch-all forward (including all the spam) from the domain to your clients personal gmail account.

But yeah, if you want to hit me up drop me a email and when I have a spare 30 mins I'll give it a once over and tell you your options. (Note: UK time here, dunno where you are, so if you email me while I'm asleep I'll get back you after coffee and I've done my morning tasks.)

GL;HF.