A dúvida apresentada coloca no mesmo plano realidades linguísticas que convém distinguir, pois evidenciam comportamento sintáticos distintos. Por um lado, estamos perante locuções e, por outro, perante pronomes relativos com os seus antecedentes.

Assim, nas frases

(1) «Ele é feio, ao passo que ela é lindíssima.»

(2) «À medida que fui explorando, tudo se me foi revelando.»

as locuções «ao passo que» e «à medida que» são formas fixas que cristalizaram com esta estrutura, pelo que não é possível introduzir um elemento novo no interior destas expressões sob pena de as tornar agramaticais ou de produzir outras realidades sintático-semânticas. Assim, a locução «ao passo que» introduz na frase (1) um valor de contraste (por essa razão é considerada equivalente a mas, por exemplo no Dicionário da Língua Portuguesa Contemporânea) e a locução «à medida que» introduz na frase (2) um valor temporal (cf. diferença da locução «na medida em que»).

No terceiro caso apresentado, a frase correta é

(3) «À velocidade a que nos movemos, não há tempo para reagir»

A frase (3) inclui uma oração subordinada relativa, «que nos movemos», que modifica o nome velocidade. Não estamos, pois, perante uma locução, mas sim perante um nome acompanhado por oração subordinada relativa. Esta construção está no interior de um grupo preposicional, «à velocidade (a que nos movemos)», que é introduzido por à, contração da preposição a com o artigo definido a, e que tem a função de modificador do grupo verbal cujo verbo nuclear é há:

(4) «Não há tempo para reagir à velocidade…»

Na oração relativa que integra o grupo preposicional, o pronome que tem como antecedente velocidade, e funciona como modificador do verbo mover-se introduzido pela preposição a, tal como aconteceria se em lugar de que surgisse o vocábulo velocidade:

(5) «Nós movemo-nos a esta velocidade.»

Por essa razão, quando o relativo substitui velocidade é antecedido da preposição que antecedia esta palavra.

Quanto ao último caso apresentado, a frase correta é, de facto,

(6) «À velocidade que escolhemos para viajar, não há tempo para reagir».

Neste caso, o pronome relativo que não é antecedido de preposição porque é complemento direto do verbo escolher, como se pode observar se substituirmos que por velocidade:

(7) «Nós escolhemos esta velocidade para viajar.»