Well, it could be due to open relays on machines that are hosted at your ISP, but if that's true, they are a really bad ISP. No respectible ISP would want that on their network.
Generally the problem you describe is caused by someone sending spam (real or perceived) that refers to one of the sites. The IP is blocked and then all the sites are not able to send mail to those that block them. These are referred to as "bad neighborhoods".
You don't like to think that your non-profit may be located "next door" to an adult site, or something else objectionable, but some servers may have hundreds, or thousands of sites hosted. The best thing to do when selecting a hosting company is to look at their "Terms of Service" or "Acceptable Use Policy" and see if they specificly ban spam and/or adult sites. If they do, then you should be ok, since they are trying to keep a "clean house".
You can ask what the IP addess will be for the server you will hosted on, and others as well, including the one the company's site is hosting on ad see if they have are blacklisted. Go to
http://www.dnsstuff.com/ and use the option for "abuse lookup" and that will tell you.
It's a good idea to use Google to check out a host you are thinking about using. Just enter the domain name like "techsoup". Most webmaster post early and often when they have bad experiences. I don't let a complaint or two bother me too much (webmasters can be cranky sometimes), but when you see a lot and few positive posts, then it's best to avoid them.