It would indeed fix this problem if sp.gov.br were added to the public suffix list (though only for São Paulo state; really, every UF-level subdomain of gov.br ought to be added to the PSL). [I noticed that you're aware of this because of your leg.br example.]
In response to the previous thread that @mnordhoff mentions, I wrote a note in Portuguese describing the problem and the reasons why subdomains of gov.br ought to be listed on the PSL (at least two states have already had rate-limit problems—São Paulo and Minas Gerais). This ended up getting sent to several people, but none of them has replied. I have also been trying to get a contact at CGI.br to raise this question with them, but we have also not gotten replies over there.
Listing domains on the PSL is easy and free, but the request is supposed to come from a "responsible party", and that's the trouble in this case. Domains that refer to subdivisions of a country are an example of an intended use featured right on the PSL home page, so I don't see any question that the PSL maintainers would view the request as appropriate.
If you'd like, I'm happy to forward you a copy of my e-mail (either for your reference or, if you find it persuasive, so that you can forward it to other contacts). Também falo português do Brasil e pode escrever ou em português ou em inglês conforme quiser. Meu endereço é o meu nome de usuário desse fórum mais @eff.org.