Infelizmente, não há uma resposta fácil para o problema, e a resposta é muito "depende" - basicamente depende do seu ISP, o provedor que está bloqueando o tráfego e o motivo do bloqueio.
Um bom primeiro passo é comunicar informações detalhadas e razoáveis tanto ao seu ISP quanto ao seu provedor de hospedagem - Seu provedor de hospedagem está pagando por um serviço (e você está pagando a eles), então eles têm alguma alavancagem e provavelmente SLAs e afins. Claro, quanto mais orçamento o anfitrião, menos isso ajuda você.
Você quer tentar fazer "traceroutes" em ambas as direções para ver o que está acontecendo e fornecê-los ao provedor - essa é a informação mínima de que eles precisam. Usar MTR geralmente é uma solução melhor, pois também mostra perda de pacotes.
Dito isto, pode ser mais fácil simplesmente migrar o site para um ISP diferente - ou obter outro endereço IP do seu provedor atual que não esteja bloqueado - tenha cuidado com os "bairros ruins".
Outro "work-arround" (que pode frustrar o propósito) pode ser colocar um proxy reverso em outro site e, em seguida, apontar o DNS para ele e fazer proxy para o provedor real. É provavelmente exagero, mas pode ser útil se você precisar mover o site ou contornar certos problemas de alcance.