I am a customer with a webhost and my account is on a shared server. The problem is, it looks like one of the other customers on the same server has gone and got the shared IP blacklisted as spam/virus. I can see the IP listed.
Because of this, my legitimate emails sent from my web application are not being sent. They either end up in the spam folder every time or are not delivered at all.
What options do I have for getting my mail sent out without problems?
Edit: I should have mentioned I'm only sending contact form submission emails and the like, no mass mailing, but the bulk mail advice supplied is good nevertheless - thanks.
There is the obvious answer of "get off this host". Perhaps an easier solution is to see if your ISP provides a "smart host" that you can setup your MTA to relay through. It also might be worth raising the issue with the ISP to consider whether the entity you are sharing the host with should perhaps be removed, if what they are actually sending spam.
Since IP-based blacklists and reputation scores are so prevalent, all mail from the same IP address is treated the same way by nearly everyone who receives email. The only way of seperating your reputation from the other users of the IP address is to get a separate IP address.
Your hosting provider may supply an SMTP smart host however this is likely to have the same problem. It will be shared with other users and hence the IP's reputation will be poor.
If you go for a VPS or a dedicated server you will get your own IP address and can run your own mail server but it's worth mentioning that this is not a set-and-forget process. Running a mail server in such a way that you maintain a good reputation and stay off blacklists requires diligence. You must process and unsubscribe bounced emails (this is very important) and also sign up for feedback loops with anyone who offers one and act on any reports you get. You may also want to run spam detection on your outbound mail. (This may or may not be relevant to you depending on the source of your emails.)
If this sounds like too much work, there are third party relaying services that handle bounces and feedback loops for you. Some of them also offer click tracking, unsubscribe links and unsubscribe replies. I don't know of any that do spam detection but it wouldn't surprise me if some of them did. Although they share their sending IP addresses with many other customers, email is usually their only business so they take great care to maintain good reputations for those IP addresses.
Long Term
The key question here is what is the risk associated with getting your emails blacklisted?
If the potential risk in terms of business impact is significant, then paying for managed email services is a good investment.
With shared hosting, there are significant risks to email delivery. Overloaded systems, hacked accounts, other people sending newsletters and similar activites lower the sending reputation of the IP. Often entire IP ranges are flagged as suspect.
Current Issue
In terms of resolving the current situation, contact your host. Send them any reports of major blacklists or examples of bounces form major ISPs.
There are many blacklists but the majority you find on blacklist check sites are not widely used. Spamhaus, Spamcop, Barracuda and similar services are the ones that can block your email to a wide number of users.
In addition to blacklist lookups, check your sender's reputation at SenderScore: https://www.senderscore.org/
Different hosts respond in various matters, but the more clear evidence you can provide that they have a wide impacting problem, the more likely they will take action.