I would not use a shared server for E-mail hosting, for this exact reason. Even if you are the only person on the IP, you need to watch out your first couple of months because the IP you have could have been misused in the past. If you find your new host’s IP on a blacklist, request a new IP from your provider.