There's two things wrong that I see.
First, as has already been pointed out, your SPF record is wrong. SPF records tell the world what IP address/es your outbound mail server sits on.
Lets consider a really simple case where outbound and inbound mail are dealt with by the same server.
v=spf1 mx -all
Looking at each part
v=spf1 - The version number of the SPF record - currently only spf1 is defined.
mx - use the IP addresses of servers found in my domains MX records
-all All in this context means every address and the - before it means hard fail.
If setting an SPF record up is daunting - you could try one of the many SPF generators such as:
However you also have another problem:
DKIM check: permerror
This suggests that your mail is being signed by the mail server but there's a problem with the DKIM record this could be anything such as
No record in DNS
Improper DKIM record in DNS
This may seem a little vague, but the first thing I'd do is to look at the DKIM signature on one of your outbound mails. Two things to note will be the d= and s= values
d= is the domain responsible for signing the mail.
s= is called the DKIM selector.
If you look for a txt record under the following record:
For example if I take a DKIM signature from Twitter
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=twitter.com;
We see that
So if we do a DIG
C:\Users\timdu>dig txt dkim-201406._domainkey.twitter.com
; <<>> DiG 9.10.6-P1 <<>> txt dkim-201406._domainkey.twitter.com
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 32288
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 1
;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 512
;; QUESTION SECTION:
;dkim-201406._domainkey.twitter.com. IN TXT
;; ANSWER SECTION:
dkim-201406._domainkey.twitter.com. 300 IN TXT "v=DKIM1; p=MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAwe34ubzrMzM9sT0XVkcc3UXd7W+EHCyHoqn70l2AxXox52lAZzH/UnKwAoO+5qsuP7T9QOifIJ9ddNH9lEQ95Y/GdHBsPLGdgSJIs95mXNxscD6MSyejpenMGL9TPQAcxfqY5xPViZ+1wA1qcr" "yjdZKRqf1f4fpMY+x3b8k7H5Qyf/Smz0sv4xFsx1r+THNIz0rzk2LO3GvE0f1ybp6P+5eAelYU4mGeZQqsKw/eB20I3jHWEyGrXuvzB67nt6ddI+N2eD5K38wg/aSytOsb5O+bUSEe7P0zx9ebRRVknCD6uuqG3gSmQmttlD5OrMWSXzrPIXe8eTBaaPd+e/jfxwIDAQAB"
We find the DKIM record which has the public key used to verify the signature and body hashes of the email.
So you need to make sure that you've got an equivalent record set up correctly.