Complain to your provider. You're paying for the service, right? They should run a properly configured mail exchange and part of that is having PTR records. If they can't manage that then it's time for a serious discussion about changing vendors.