Elias, boa tarde!
Fiz uns testes com o georreferenciamento por cep, usando ggmap::geocode(). Na verdade, dá pra fazer uma avaliação da acurácia pelos campos type e loctype retornados quando se utiliza a opção "output=more". Pelo que pude entender, endereços "precisos/acurados" são retornados com a indicação "street_address" em type e as demais formas são aproximações. No entanto, códigos "postal_code" são melhores que "postal_code_prefix".
### <code r>
require("ggmap")
# geocodeQueryCheck()
adr1 <- c('Rua Toshinobo Katayama, 178, Dourados, MS, Brazil, 79806-030', ### endereço completo
'Rua Toshinobo Katayama, 171, Dourados, MS', ### endereço completo
'Dourados, MS, 79806-029', ### não cadastrado, prefixo válido
'Dourados, MS, 79899-333', ### cep inexistente
'Dourados, MS, 79806', ### apenas prefixo
'Dourados, MS, 79806030', ### cep correto
'Dourados, MS, 79823460', ### cep correto
'Dourados, MS, 79804970') ### cep correto, zona rural
res1 <- geocode(adr1, output="more")
res1[c(1:4, 10)]
# lon lat type loctype postal_code
# 1 -54.80372 -22.23004 street_address rooftop <NA>
# 2 -54.80460 -22.22413 street_address range_interpolated <NA>
# 3 -54.80027 -22.22395 postal_code_prefix approximate <NA>
# 4 -54.79138 -22.22623 bus_station approximate <NA>
# 5 -54.80027 -22.22395 postal_code_prefix approximate <NA>
# 6 -54.80409 -22.22820 postal_code approximate 79806-030
# 7 -54.83732 -22.21741 postal_code approximate 79823-460
# 8 -54.80988 -22.21471 postal_code_prefix approximate <NA>
### </code>
Testando apenas os primeiros 30 ceps do arquivo que você disponibilizou...
### <code r>
tmp0 <- read.table(url0, head=T, nrows=30)
adr2 <- paste0("Curitiba, PR, Brazil, ", tmp0[,1])
res2 <- geocode(adr2, output="more")
cbind(tmp0, res2[c(1:4,10)])
table(res2$type)
# route postal_code_prefix postal_code
# 2 14 14
### </code>
Nesse pequeno teste, 16 consultas retornaram resultados muito imprecisos (route , postal_code_prefix) e os demais são poucos precisos (postal_code).
Desse modo, acredito que não há grande vantagem em consultar todos os ceps e o número de consultas poderia ser diminuído consideravelmente se eles fossem 'generalizados" . A opção mais radical seria fazer a consulta pelos prefixos (primeiros 5 dígitos) e outras mais brandas seriam algo do tipo:
df <- read.table(url0, head=T, nrows=1000)
df$cep2 <- round(df$cep/100)*100
un <- unique(df$cep2); length(un) # 135
Nesse caso seriam 135 consultas ao invés das 1000 iniciais, o que facilitaria bem a tarefa. Logicamente, haveria uma perda ainda maior de precisão/acurácia. Resta saber se a perda é tolerável/aceitável.