Smarter SPF record check
Currently the check for SPF record require that the value is exactly as it's indicated in the guide, but this is needlessly restrictive, or quite dumb. First if you have a Server/VPS there is the chance that the machine sends email to the admin directly, and for this to work you need a value like "a" in the SPF record to allow to send email from the machine that hosts the domain. Another problem is newsletters, that are frequently sent through third-party services and these need their own value in the SPF record.
AdminTutanota Support (Admin, Tutanota) commented
As a workaround: just set the strict entry for a few minutes, do the domain validation in Tutanota, and change it to your softer entry afterwards.
I too have this problem. Please allow other valid SPF records.
For example, "v=spf1 include:spf.tutanota.de include:mailgun.org ~all" is valid but the app will not accept it.