Hi there,
First of all they could be blocked and listed on spam lists, such as spamcop. If someone has been spamming via the same machine you are on and they have not followed this up then they could be on this list. Some email servers link directly to these lists and basically block all email from them that are listed in these spam directorys.
Moving to someone else can be hard, one thing you must do is plan it carefully and of course, FULLY inform your clients. Keeping them in the light about delays, problems and hopefully success will do nothing but benifit you and the business.
You have to do what you have to do, if you need to move its best to do it before you get too big, but make sure that your provider can support you enough and maybe pay alittle bit more.. it goes alot way.
Cheapest often is not the best (I do know there are alot of cheap hosts out there, but often, they oversell, run into problems etc.. best be safe than sorry!)
If you have any more questions.. let me know
Craig.