I wouldn't recommend synthesizing SPF records for nonexistent domains (e.g. via wildcard records). Most providers will treat NXDOMAIN as a stronger spam signal than SPF hardfail, some even by rejecting the mail outright.
By decreasing your spamminess with some smaller providers that just ticked SPF off a a checklist, you may be increasing your spamminess with other providers that actually care. 
For existing domains, explicit SPF records may indeed be a good idea. Since email falls back to A records if MX records don't exist, even a great implementation will allow at least one server to send mail.