Received-SPF: unknown domain of _netblocks2.google.com uses a mechanism not recognized by this client

We've configured SPF for our Google Apps For Your Domain domain some time ago, and resources like mail-tester.com validate it as setup correctly (we also have DKIM, etc). For the past year however, we've been getting a lot of "Mail not delivered" messages and replies to strange emails from our domain we've never sent. Sometimes they include the headers from the original email and they look like this:

Received-SPF: unknown(brass9.com: domain of _netblocks2.google.com uses a mechanism not recognized by this client)

In this case the spam service appears to be "Spam Arrest," based on other headers.

So my question is, what can I do to stop this flow of invalid email from our domain? And what can I do to get services like the above to understand our SPF record? Is the default Gmail SPF record not fully compatible with some common spam services?

There's much debate over whether the tilde belongs in a Gmail SPF record, so we've tried changing our SPF record to be more strict:

v=spf1 include:_spf.google.com include:aspmx.googlemail.com -all

But we still see emails like the above. Is there anything we can do to be better netizens?

Note that this question is somewhat similar to this one, except this is for sending from Gmail - theirs was about getting their SPF record to be accepted by Gmail.