Step 1 – Separate your mail traffic from your browsing traffic

One of the biggest problems to having your mail delivered is being listed on one of the many available spam lists like Barracuda, SpamCop, or SpamHaus; an event called blacklisting. Once listed on these services, any messages sent to any organization that uses them will be actively blocked. For details on these types of lists, see the DNS Blacklist article on Wikipedia.
Unfortunately, getting on a blacklist is easy; getting off them is often not.
To see if your mail server is on any of the common blacklists, simply navigate to mxtoolbox.com and use their Blacklist tool. Just enter the public IP address of your mail server, click on the Blacklist Check button, and in a few moments you will see whether that address is listed on any of roughly 100 public blacklists. If you find that your mail server address is blacklisted, don't panic. Simply browse to the main website of the blacklist your server is listed on and read for instructions on how to request to be removed. Many times, they will provide you with greater detail on why you were blacklisted in the first place, such as an open relay, unsolicited bulk email, etc. Simply correct that issue, request the delisting, and unfortunately wait. It often takes roughly 1 business day to get delisted.
A common mistake made by many organizations that leads to blacklisting is the use of the same public IP address for the mail connector as the remainder of the organization's browsing traffic. While this configuration greatly simplifies the firewall configuration, it exposes the organization to potential blacklisting. This is because any machine on the network compromised by a spambot or other malware, whether it is owned by the organization or not, can lead to blacklisting. This is because all blacklist sites use the IP address to signal a block rather than the apparent DNS host or domain name. Since the IP address is the key, any machine that gets NAT'ed to the same address as your mail server can potentially result in your mail server being blacklisted, so the fewer devices sharing an address with your mail server the better.
While to implement this you may need to work with your ISP to get a slightly larger IP range on your service; but if you simply take the time to configure the firewall to separate the end-user traffic from the email traffic, you will save yourself a lot of problems down the road. If you are on a tight budget and need to cohost services on the same address as you really can't afford separate IP addresses for your major services, at the very least separate the server and workstation traffic to separate IP addresses. It is far less likely, but not guaranteed, that your FTP or Web Server will be the host of a spambot than the whole collection of workstations and laptops using the same firewall.