ICMS sobre Transporte

Como funciona a cobrança de ICMS em prestação de serviços de Transporte em outro estado?

A empresa de meu cliente está situada em Tocantins, porem, ele tem ônibus em Goiás, em Brasília e aqui em Tocantins também, os ônibus só cruzam estados quando estão voltando pra sede em Tocantins pra fazer alguma manutenção, mas no caso de Goiás e Tocantins rodam por vários municípios do estado. Fui informado que dentro do estado do Tocantins sou isento de ICMS, isso procede?

E nos serviços nos outros estados e no DF como devo proceder?

A NF tem que ser de Serviços com ISS, ou DANF com ICMS???

Nas prestações de serviços de transportes intermunicipal, deve se emitir nota fiscal de Prestação de Serviços com o ISS. Ou seja o serviço esta sendo executado dentro do próprio município.
Quando o serviço é de um transporte entre cidades, ou seja inicio em determinada cidade e termino em outra, ai de fala na emissão do CTR com destaque de ICMS seguindo a legislação vigente. Quanto a isenção do ICMS em TOCANTINS não tenho este conhecimento por estar situado em SP, mais se nossos colegas, não tiveres esta resposta, mais a tarde farei uma pesquisa e te informo.