Emails are regularly blacklisted due to being hosted on a shared (blacklisted) server. What can I do besides moving away from this shared server?
email is a completely different service to http. It is perfectly normal to have one pointed at one provider and the other at another.
mx records are used when receiving mail, your blacklisting is a problem when sending mail. You need to send mail using a different server and in this case google should be acceptable.