SPF softfail error

Hi All,  

We host the DNS and website for a client but they have their mail server at their location.  We have an SPF record setup for them which has never given us a problem in the past.  
SPF record:  v=spf1 mx a:exchange.clientdomain.com include:spf.constantcontact.com ~all
We have an mx record = exchange.clientdomain.com
We have an A record =
Now, when one of the users sends an email to a yahoo address with a group of other people, she is receiving a softfail error:  
"Message from yahoo.com.
Unable to deliver message to the following address(es).
This user doesn't have a yahoo.com account (email@yahoo.com) [0]
--- Original message follows.
The original message is over 5K. Message truncated.
Return-Path: <client@clientdomain.com>
Received-SPF: softfail (mta1039.mail.re4.yahoo.com: domain of transitioning client@clientdomain.com does not designate as permitted sender)"

Now, she can send an email to this yahoo address individually and it works w/o a hitch.  I'm new to DNS so help is greatly appreciated.  BTW, I did not setup the SPF record, it was in place when our DNS guy left.  I tested in http://www.kitterman.com/spf and here is what I get, which baffles me even further because their other tests passed for the same record:
"SPF records are primarily published in DNS as TXT records.
The TXT records found for your domain are:
"v=spf1 mx a:exchange.clientdomain.com include:spf.constantcontact.com ~all"
SPF records should also be published in DNS as type SPF records.
No type SPF records found.
Checking to see if there is a valid SPF record.
No valid SPF record found of either type TXT or type SPF."

Please help.
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Ernie BeekExpertCommented:
One thing, I hope it's not a type but afaik the spf record should end with -all (with a minus sign) and not ~all with a wavy thing (don't know how it's called, tilt or something?).
Ernie BeekExpertCommented:
of course type = typo :-~
kimhaddockAuthor Commented:
I had a ' - ' and changed it to a ' ~ ' to see if that made a difference...<grasping at straws>
Acronis True Image 2019 just released!

Create a reliable backup. Make sure you always have dependable copies of your data so you can restore your entire system or individual files.

Ernie BeekExpertCommented:
Ok, checked it and ~ is allowed. ~ gives a softfail and - gives a fail. So you're getting the fail because it looks like a:exchange.clientdomain.com is not accepted by yahoo. You might try replacing that with just 'a'.

So: "v=spf1 mx a include:spf.constantcontact.com ~all"
I assume exchange.clientdomain.com falls withing the range,
kimhaddockAuthor Commented:
Question - why does yahoo accept it when the sender is sending an email to just the yahoo receipient but yahoo does not accept it when there are multiple receipients?
Ernie BeekExpertCommented:
Good question. I know that yahoo is kind of picky end sometimes irradical when blocking/allowing mails. The only thing I can think of at the moment is that it only checks SPF when mails are sent to groups because of the extra resources it takes to check.
The thing is, are you able to check the functionality of the spf against another server which check for spf with incoming mail? Or, in other words, did you ever had a similar deny with another server?

One more thing:
We have an mx record = exchange.clientdomain.com
We have an A record =

Does this mean that exchange.clientdomain.com resolves to
kimhaddockAuthor Commented:
No, we've never had this issue occur with other servers.  She is able to send emails all over the place w/o incident.  Yes, when I ping 'exchange.clientdomain.com' I do receive the correct IP.  So, we just blame yahoo?  lol
Ernie BeekExpertCommented:
Looks like it (again). I've had several issues where everything was working, except with yahoo :(
Just browse through EE.......
I could say: try to contact them, but they aren't that easy to get in touch with.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
kimhaddockAuthor Commented:
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.