Allright, this was a tricky one. Zimbra uses Postfix, but one cannot just manually edit the configuration files, as zmconfigd will be more than happy to overwrite your changes.
So, after installing policyd-spf-python, using the source of course, as Zimbra does not record Postfix to be installed, you must edit the following:
In /opt/zimbra/common/conf/master.cf.in and /opt/zimbra/common/conf/master.cf.proto, add:
scache unix - - n - 1 scache policyd-spf unix - n n - 0 spawn user=zimbra argv=/usr/local/bin/policyd-spf
In /opt/zimbra/conf/zmconfigd/smtpd_recipient_restrictions.cf add:
reject_unlisted_recipient check_policy_service unix:private/policyd-spf
The restart zmconfigd and zmmta.
With thanks to Linuxbabe.