You will have that problem from time to time with any "Cheap" host. Nothing they can do about it. The black listing places put servers on lists because a lot of times, people forward their email to their gmail, hotmail and other accounts without using any spam filtering. This will get the server blacklisted almost as fast as a spammer attacking someones form and sending a blast of spam.
All shared servers get listed from time to time. The host has to keep constant watch to see when they get listed, find the problem, solve it, then try to get unlisted... it is a never ending battle.
The best thing you could do if you need to keep with a Cheap Host... is set up your email at your domain registry. Almost all of them offer it for a buck or so a month. That way, you get your cheap hosting, and your email works too.
The host may well have not been blacklisted when you signed up. This happens without notice to the host, all the time.
Here is a good place to check to see if your server is black listed: http://www.mxtoolbox.com/blacklists.aspx?
Sometimes you can find why, so you can alert the host to get off the list asap.
However, without knowing the mail server IP of the host you are thinking about signing up at, there is no way to tell ahead of time.
Consider using external mail company to send your mail -- like AUTHSMTP for $24 per year. You still use your regular FROM addresses to send mail. I have had many clients use their service to get around ISP blocks and have tried them myself.