Mailgun mails bouncing, possible DNS records are wrong

This has probably been asked and answered before, but I'm a bit lost because I don't know what's happening and therefor don't know what to look for. I would not only like a solution of course, but I would also like to understand what's happening. I have a technical background, but in software development. Servers, DNS records, etc is a bit new to me (although I've managed).

I'm running a web application on shared hosting. I have access to a Plesk control panel (I believe 12.5). The domain name is registered at another company. And for sending mails, I'm using Mailgun (calling their API).

Now, some mails bounce (others don't), with messages like:

• Sender address rejected: Domain not found
• sorry, your domain does not exists.

When I use MXToolbox, an MX Lookup looks fine. But when I test the email server (with MXToolbox), I see the following messages:

• Reverse DNS does not match SMTP Banner
• Warning – Does not support TLS

I don't think the second is a problem (?), but the first one might be? When I do a check for SPF I see:

• DNS Record not found

Should I fix this? (I've heard about SPF in mail contexts) This question seems to suggest I should add an SPF record, but I currently can't in Plesk 12.5.

On the other hand, Mailgun itself says everything is fine (apart from the records but as I read it, they're not important for sending mails?):

So what's going on here? And how can I fix it, or what should I know to dig deeper?

Update

The domain this is happening on is peergroups.be

An example of headers of a mail that was received:


Delivered-To: peter.morlion@gmail.com
Received: by 10.100.161.143 with SMTP id q15csp289063pjc;
Wed, 24 May 2017 04:10:04 -0700 (PDT)
X-Received: by 10.98.93.217 with SMTP id n86mr37944933pfj.113.1495624203335;
Wed, 24 May 2017 04:10:03 -0700 (PDT)
Authentication-Results: mx.google.com;
spf=pass (google.com: domain of bounce+3c1c7e.55be3c-no-reply=peergroups.be@mg.peergroups.be designates 198.61.254.51 as permitted sender) smtp.mailfrom=bounce+3c1c7e.55be3c-no-reply=peergroups.be@mg.peergroups.be;
dkim=pass header.i=@mg.peergroups.be
Received-SPF: pass (google.com: domain of bounce+3c1c7e.55be3c-no-reply=peergroups.be@mg.peergroups.be designates 198.61.254.51 as permitted sender) client-ip=198.61.254.51;
Received: by 10.99.134.67 with POP3 id x64mf19905540pgd.0;
Wed, 24 May 2017 04:10:02 -0700 (PDT)
X-Gmail-Fetch-Info: no-reply@peergroups.be 4 peergroups.be 110 no-reply@peergroups.be
DomainKey-Status: good
Received: from so254-51.mailgun.net ([198.61.254.51]) by home with MailEnable ESMTP; Wed, 24 May 2017 06:15:04 -0400
DKIM-Signature: a=rsa-sha256; v=1; c=relaxed/relaxed; d=mg.peergroups.be; q=dns/txt; s=pic; t=1495620904; h=Content-Type: Mime-Version: Subject: From: To: Message-Id: Date: Sender; bh=60eeErLSy3DUfbYC4arXt0KAzdkuCC532GBme+wUcGk=; b=ky0zW94QsXQqkl8LFf+S0YI87ltc92JRKbl4sxN2HKe6ZJwsBBfIJMr5IQGg+LVBCxb0wt3b jcAVWRGFzHVXmIk/y5Ejphp1LwrkKKg62rocD6Jx4ZZFLsDiTMaXa3k108wnEhQuK4vbiEZP QUtpRzdcoaYC5AtFzoaQ9PYPU6g=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=mg.peergroups.be; s=pic; q=dns; h=Sender: Date: Message-Id: To: From: Subject: Mime-Version: Content-Type; b=O0C2WmpWCejy1cmQF1zc8spQo3zdEe7EV14Niynve2ilpUBguylHYU/muTCkD+n6saCKjK fvyjkBsvkxI6r2dA1myRBq8RQ9jZjgFxPjG6QgVSw9xObYz69QssRGrEAIZonOUMjoTzqrbd uDAM11KpxXB488y9NzH8LmzaXTAig=
Sender: no-reply=peergroups.be@mg.peergroups.be
Date: Wed, 24 May 2017 10:15:04 +0000
X-Mailgun-Sending-Ip: 198.61.254.51
X-Mailgun-Sid: WyIxMjkwYSIsICJuby1yZXBseUBwZWVyZ3JvdXBzLmJlIiwgIjU1YmUzYyJd
Received: by luna.mailgun.net with HTTP; Wed, 24 May 2017 10:15:03 +0000
Message-Id: <20170524101503.72580.5AE8265694D87481@mg.peergroups.be>
To: no-reply@peergroups.be
From: Peergroups <no-reply@peergroups.be>
Subject: Some subject here
Mime-Version: 1.0
Content-Type: multipart/alternative; boundary="c9281a23246040cfb8a7081ab45d40f5"
Return-Path: <bounce+3c1c7e.55be3c-no-reply=peergroups.be@mg.peergroups.be>