SPF softfail domain does not designate IP as permitted sender
I found a solution, in the end I added the mail server IP to the TXT record and now gmail accepts the sender. If anyone is interested, this is how it looks like:
v=spf1 ip4:xxx.xxx.xxx.xxx include:mailgun.org ~all