Se 1 trilhão de Tianhe-2, o super computador mais rápido do mundo, fossem usados para gerar endereços, gerariam ~ 2^80 endereços por segundo. Assim, em 2^176 segundos todos os endereços seriam esgotados.
2^176 segundos equivalem a ~ 10^38 bilhões de anos, isso é 10000000000000000000000000000000000000 de vezes maior que a idade do universo desde o big bang até hoje.
Ele não consegue essa garantia, é que as chances de colisão são tão ridiculamente pequenas que não precisa se preocupar com isso. O que ele faz pra gerar um endereço pra você quando você instala, digamos, o core QT, é catar dados aleatórios no seu computador pra servir de "seed" pra chave. Por isso é recomendado que você gere um seed o mais aleatório possível, por exemplo offline, pra gerar sua pvt key.
Sim, vc pode gerar offline uma pvt key, o protocolo não precisa ler essa pvt key. O que o protocolo lê é a transação que enviar fundos para a public key que vc gerou offline a partir dessa pvt key (vc pode ir nos sites geradores de paper wallet e salvar a página pra fazer tudo isso). Quando você importar essa pvt key pra alguma carteira online, sua carteira mostrará os fundos lá, pois o protocolo sabe que sua pvt key é associada àquela public key onde vc recebeu fundos.
Resumindo: pra receber fundos vc nem precisa nunca estar online, pra gastar fundos sim.