Our IP has been removed from the blacklist so most emails are now sending correctly. The only remaining problem seems to be with tiscali/talktalk which seem to still think we're in the blacklist even though we aren't. Hopefully they notice this soon and start accepting email!
As a separate task I will look into integrating Voice with an email sending service such as Postmark or SendGrid. The idea is that we send the emails via them and they route via different IP addresses and continually monitor for bounces and re-route until they succeed.
On the plus side this would reduce the chance of future emails failing. The downside being integration time and ongoing subscription fees.
Thanks
Joe