SPF vs. DKIM - The exact use cases and differences
Solution 1:
SPF has many more rankings than Pass/Fail. Using these in heuristically scoring spam makes the process easier and more accurate. Failing on account of "advanced setups" indicates the mail admin didn't know what he was doing in setting up the SPF record. There's no setup that SPF can't account for correctly.
Cryptography doesn't work in absolutes, ever. The only crypto allowed in DKIM usually takes significant resources to break. Most people consider this safe enough. Everyone should evaluate their own situations. Again, DKIM has more rankings than just Pass/Fail.
One example where one would benefit from using both: sending to two different parties where one checks SPF and the other checks DKIM. Another example, sending to a party with content that would normally rank highly in spam test, but that is offset by both DKIM and SPF, allowing the mail to be delivered.
Neither are required in most cases, though individual mail administrators set their own rules. Both help to address different facets of SPAM: SPF being who is relaying e-mail and DKIM being the integrity of e-mail and authenticity of origin.
Solution 2:
This was answered some time ago, but I think the accepted answer lacks the point of why both must be used together to be effective.
SPF checks the IP of the last SMTP server hop against an authorized list. DKIM validates the mail was initially sent by a given domain, and warrantees its integrity.
Valid DKIM signed messages can be used as spam or phishing by being resent with no modification. SPF does not check message integrity.
Imagine a scenario where you receive a valid DKIM signed email (from your bank, a friend, whatever), and you find a good way to exploit this mail without modification: then you can just resend this mail thousands of times to different people. As there is no modification of the mail, the DKIM signature will still be valid and the message will pass as legitimate.
Anyway, SPF checks the origin (real IP/DNS of SMTP server) of the mail, so SPF will prevent the forwarding of the mail as you cannot resend a valid mail through a well configured SMTP server, and mail coming from other IPs will be rejected, effectively preventing the resending of "valid" DKIM messages as spam.
Solution 3:
Here are some reasons you should always publish both SPF and DKIM.
Some mailbox providers only support one or the other and some support both but weight one more than the other.
DKIM protects email from being altered in transit, SPF does not.
I'd add DMARC to the list, too. What's the downside to always publishing full email auth?