After trying a few SPF values, the one that seems to convince Google the right server sending out has this template:

v=spf1 ip4:<ip_of_your_mail_server> include:<domain_of_your_mail_server> ~all