Why does sending an email go to the Spam folder?

We have a new domain. Sending email to Gmail, HotMail results in the messages sent to the Spam folder.

I discovered that the static IP address for our email server was blacklisted on spamhaus.org. The IP address was changed to a different address.

When I send an email to gmail I find this: (Received: from proxy) and it goes to the Spam folder. I think it should be (Received: from)?

How does this get fixed?

I don’t actually have my own mail server it is outsourced to a hosting provider.

Since your last reply in the comment section (SMTP Reverse DNS Resolution Reverse DNS Resolution - No PTR Record found) is basically showing what's going on, I can move this now to Answer.

You (or your external partner, NetworkSolutions) have to contact your ISP or Cloud hosting provider to create that PTR record for your mail server.

Otherwise your mails' origin cannot be verified.