Nearly all providers will give you a new IP if your old one got blacklisted before it was assigned to you.

Note; 'clean IPs from unassigned netblocks' are not necessarily good. see bogon filtering[1] - still, running your own mailserver is not an impossibly difficult task.

[1]http://en.wikipedia.org/wiki/Bogon_filtering