Em minha opinião, nenhuma dessas traduções é muito feliz.
A perífrase costumar + verbo exprime geralmente um valor de aspeto habitual, embora nem sempre, como mostra Oliveira com a frase «eu costumava ter uma amiga com inúmeras pulseiras. Ela parou quando começou a deformar o braço». A frase não será porventura muito elegante, mas também não a rejeitaria (o mesmo se aplica àquela que o Jacinto dá como inaceitável: «eu costumava detestar couves»). Este uso não habitual aplica-se com muito mais força ao inglês used to (Oliveira cita o exemplo the Temple of Diana used to stand at Ephesus). Outro exemplo: you didn't use to be this way deve traduzir-se por não eras assim, embora não me pareça impossível não costumavas ser assim.
Em todo o caso, nas tuas frases há um estado habitual e um verbo que descreve geralmente um processo. Na seguinte frase (repara que substituí nunca por não):
Não costumamos caminhar nessa rua.
temos duas interpretações: como pretérito perfeito (=caminhámos em Portugal) e como presente.
Como presente, a forma é perfeitamente aceitável, mas refere-se a um estado de coisas presente; uma frase semelhante é:
Não caminhamos geralmente nessa rua.
Retirando o geralmente, temos ainda uma leitura habitual, mas que não admite as caminhadas excecionais que as frases com costumar admitem.
Mas claramente a frase original em inglês não descreve um estado presente. Consideremos a possibilidade de ser um pretérito perfeito, equivalente (em Portugal) a:
Não costumámos caminhar nessa rua.
Pesquisando no corpusdoportugues.org, encontramos exatamente zero exemplos relevantes para [costumar].[vJ*]
(costumar no pretérito perfeito); no CETEMPúblico temos apenas um exemplo para a pesquisa equivalente [lema="costumar" & temcagr="PS_IND"]
:
Numa relação de forças menos óbvia, com soberanias a respeitar, escolheu-se o que costumámos designar de «via lenta» de introdução de uma moeda única [...]
Parece-me que é um erro e que o autor queria escrever costumamos designar.
Portanto praticamente inexistem ocorrências de costumar no pretérito perfeito. Este ocorre quase sempre no pretérito imperfeito (costumávamos), o que é de esperar, dado que o pretérito imperfeito tem, tal como o presente, leituras habituais (Quando havia sol, caminhávamos nessa rua).
A razão por que a frase
??Nunca costumávamos caminhar nessa rua.
me parece pouco admissível deve-se à presença de nunca, que entra em conflito com costumávamos. Nunca é demasiado categórico para usar com costumávamos; o último deixa espaço para exceções. Repare-se também na impossibilidade/marginalidade duas frases seguintes:
*Nunca caminhávamos geralmente nessa rua.
??Geralmente, nunca caminhávamos nessa rua.
Se quisermos dizer nunca teve o hábito de (significado que é algo diferente), então temos de escrever:
Nunca tivemos o hábito de caminhar naquela rua.
Uma pesquisa nos corpora confirma a raridade da combinação de nunca com costumar. Fazendo uma pesquisa por "nunca" [lema="costumar.*"]
no CETEMPúblico, temos zero resultados e apenas dois com a pesquisa correspondente no corpusdoportugues.org.