Creating a Missing SPF Record

Dear Experts,

Some of our outgoing emails are marked as Spam to the Receiver's Mail Servers since we do not have an SPF Record.

Our Environment:
1 Forest
1 Domain
2 Windows 2012 Domain Controllers (one primary, one backup)
1 On-Premise Exchange Server 2013
1 Cisco Anti-Spam Server which is our email gateway

For the purposes of this question please find an example of domain, mx records and IPs:

Domain: example.com
Anti-Spam Server: mail.example.com
Public IP of Anti-Spam Server: 176.35.29.17
Internal IP of Anti-Spam Server: 10.1.1.51
Internal IP of Exchange Server: 10.1.1.43
Public IP Range: 176.35.29.16 (first IP), 176.35.29.31 (last IP)

I have created an SPF record by using the relevant wizard/tool of MXToolbox - SPF Record Generator

Type: TXT
Host/Name: example.com
Value: v=spf1 a mx a:mail.example.com ip4:176.35.29.16/28 ~all

According to the message headers provided from the recipient in which our email was blocked, the mail.example.com with IP 176.35.29.17 has no SPF record.

Q1) Is the above SPF generated Text correct?
Q2) Should the SPF include both FQDN and all the range of our Pubic IPs? (or either FQDN or Pubic IP is enough)
Q3) Is the CIDR accepted as a format on an SPF record?
Q4) Should we use all the Range/IP Block of our Public IPs or only the IP 176.35.29.17 of mail.example.com?
Q5) I have seen that some other users mention Internal IPs instead of Public ones. Which is correct?
Q6) The SPF record should be published only in my Domain Controller or should I also create a Record in my ISP Provider (as I did with the MX Records)?
Q7) Once the record is added can I SPF lookup immediately (by usinig MX Toolbox Tool) or it will take effect after some time?

To help me out, you are kindly requested to use the numbering for each question you are answering to.

Thanks in advance,
Mamelas