Ideas so far
Well, many choices. If you think SPF helps, go for it. DomainKeys and SPF are all origin controlled, though, so it won't result in less spam, it will just help prevent spammers from sending mail impersonating your domain.
If you are getting warnings from something, what are they? Fixing ones caused by queries is probably a good thing, but many tools artificially warn about things that the tool author thought important, but in reality are not so critical.
Also consider DNSSEC, and adding your KSK to http://dlv.isc.org/