One of the most important things I learned about SPF records was that the entire record had to be under 256 bytes. We were sending out emails from multiple servers on one domain, and were having so many deliverability issues because the SPF record had too many entries in it and would be seen as invalid by some spam firewalls. Once I cleaned up the record and split some email out to subdomains our delivery rates went way up. But of course as others mentioned SPF is just the beginning. DKIM, DMARC, reverse records, etc are all very important as well.
> One of the most important things I learned about SPF records was that the entire record had to be under 256 bytes.
It sounds like this is a case of buggy implementations. You can have TXT and even SPF records longer than 255 bytes. The fundamental issue is that TXT records are composed of segments of up to 255 bytes each, where each segment has an 8-bit length header. As Resource Records (RR) individually, as well as DNS packets as a whole, have a maximum length of 65535 (because of 16-bit length headers), DNS supports TXT RRs of approx. 256 segments, 255 bytes each.
It's not too surprising implementations might be buggy in this respect. It's a rather esoteric aspect of the TXT RR specification. (If only because few people, including developers of DNS-related tools, bother actually reading the specification!) And unfortunately neither the popular rfc4408-tests.yml nor rfc7208-tests.yml test suites seem to have a test case for long TXT records. Even if a test had been included it likely wouldn't have caught many violators as it's actually a matter of the low-level DNS library providing the proper interface(s), many DNS libraries are deficient in how well they expose DNS record parsing or packet injection interfaces, and most SPF libraries would have likely integrated the test suite at a higher level that didn't involve actually making queries using a low-level DNS library, which can be difficult to do.
That said, RFC 4408 says that,
> SPF implementations MUST limit the number of mechanisms and modifiers that do DNS lookups to at most 10 per SPF check, including any lookups caused by the use of the "include" mechanism or the "redirect" modifier.
IME experience this limit is rather low and many, many SPF policies require more than 10 queries. (And if you need SPF policies larger than 255 bytes, you're probably skirting this or other similar limits.) When I was writing and deploying my own implementation I very quickly realized I needed to increase the minimum maximums, but choosing that value is a total crap shoot.
SPF records large than 256 bytes are pretty common. See e. g. aspmx.sailthru.com (1st what found right now). You just have to split text into multiple strings, but don't forget to add a space after or before a derective, because strings are joined without an extra spaces: https://tools.ietf.org/html/rfc7208#section-3.3
May be there are buggy implementations which don't understand this, but doubt they are common.
You can fix this by putting a single SPF entry for each envelope/returnpath domain. SPF scales smoothly that way without any need to overload a single top level record with entries. This will pass DMARC as well.
