I have used www.gradwell.com for email-only hosting (including outgoing). They are very reliable and I very much doubt they would ever be blacklisted. A bit pricey though.

I used to have email with Easyspace and they outsourced to www.everyone.net who's prices look reasonable.

As far as blacklisting you can easily check by searching in Google Groups on the provider name and then finding which IP address they send with and searching at http://www.ordb.org/lookup/

The only ones you really need to consider are Spamhaus's SBL and XBL lists, and possibly SPEWS. By the way SBL/XBL are extremely effective - anybody running a mail server is recommended to give it a try.

Gareth