Is it OK to have multiple TXT records for a single domain containing different SPF entries?

A remote recipient domain is rejecting mail on the grounds of SPF and I think it's because the sender has SPF configured incorrectly.

When I run dig, I see:

[fooadm@box ~]# dig @8.8.8.8 -t TXT foosender.com

; <<>> DiG 9.3.6-P1-RedHat-9.3.6-20.P1.el5_8.6 <<>> @8.8.8.8 -t TXT foosender.com
; (1 server found)
;; global options:  printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 30608
;; flags: qr rd ra; QUERY: 1, ANSWER: 2, AUTHORITY: 0, ADDITIONAL: 0

;; QUESTION SECTION:
;foosender.com.              IN      TXT

;; ANSWER SECTION:
foosender.com.       14039   IN      TXT     "v=spf1 include:spf.foo1.com -all"
foosender.com.       14039   IN      TXT     "v=spf1 include:_spf.bob.foo2.com -all"

;; Query time: 26 msec
;; SERVER: 8.8.8.8#53(8.8.8.8)
;; WHEN: Tue Jan  7 09:45:38 2014
;; MSG SIZE  rcvd: 146

Is this a valid setup? It seems strange to me that there are two separate records (each with hard fails). Shouldn't everything be in a single record?

I would expect the proper TXT record to be:

v=spf1 include:spf.foo1.com include:_spf.bob.foo2.com -all

Solution 1:

No. You are right. See RFC 4408, section 4.5.

Records that do not begin with a version section of exactly "v=spf1" are discarded. Note that the version section is terminated either by an SP character or the end of the record. A record with a version section of "v=spf10" does not match and must be discarded.

If any records of type SPF are in the set, then all records of type TXT are discarded.

After the above steps, there should be exactly one record remaining and evaluation can proceed. If there are two or more records remaining, then check_host() exits immediately with the result of "PermError".

If no matching records are returned, an SPF client MUST assume that the domain makes no SPF declarations. SPF processing MUST stop and
return "None".

Solution 2:

This SPF setup is not valid. In case there are multiple records found, the record selection should produce an error as result. See RFC 7208, section 4.5 on selecting records: