Shared hosts can get their (mail) servers blocked (on quite a regular basis) once a few people on that server start sending out spam etc. Luck of the draw, depending on what server you get placed on, and who your "neighbors" are.
eg. host xxxxxxx.com[xxx.xx.xx.xxx] said: 550-Message rejected because (c5.xxxxxx.net) [xxx.xx.xx.xxx] is blacklisted at 550 dnsbl.njabl.org
So, that's an example of me (webmaster) sending e-mail to member, who's host has picked up that my server is temporarily on the dnsbl.njabl.org blacklist.
Oh, and i would have checked my mail logs long ago, but this particular hosting company (Servage) doesn't give you direct access, because of the way their servers are structured (logs are mashed together, not separated per account).