Sim.
Tudo que vc navega passa pelo provedor e fica registrado no sistema deles, porém só com a justiça e a assinatura de um juiz eles podem revelar para a polícia ou alguém.
Então se vc viu algo errado na net fique tranquilo.
Mas se for algo errado como por exemplo pornografia infantil a polícia civil tem permissão para rastrear e ver o histórico, obviamente eles fazem isso dps que o juiz assina um mandado.
Sim, sempre é possível. Usar VPN dificulta bastante o rastreamento (é o que chineses fazem para driblar o firewall do Partido Comunista da China) mas não impossibilita.
cara, esse lance de 'anonimato' é pura ilusão!
é comum você digitar algo aleatório no seu navegador e depois receber uma propaganda sobre essa parada em uma rede social ou no Youtube.
Sim, fica em uma espécie de proxy server deles, com teu histórico de acesso. Daí é necessario que tu use uma rede que promova obfuscacão, como TOR, ou uma VPN de alta segurança. Se for uma VPN, algo que prefiro, cria-se um túnel virtual criptografado entre você e ela e tudo o que acessar da rede externa ficará na ponta de lá, teu provedor não poderá rastrear seus pacotes.
Pode conectar uma vpn na outra e aumentar o nivel de anonimato. Estude.