I will add an spf record for the domain

Do it, and come back after the record has propagated through the DNS.

Don't send mails from your CGI on your web server, ask your provider/hoster for an existing mail server and let that server handle the mail delivery. The provider's/hoster's mail server usually has a better "reputation", which leads to a reduced number of false spam reports.

Alexander