Já aqui se disse que nem sempre é possível determinar a origem histórica das expressões idiomáticas. É o caso.
Note, porém, que a expressão «uma vez sem exemplo», que realmente significa «excepcionalmente», é perfeitamente regular no que se refere à elipse do verbo, à semelhança de «um bife sem batatas fritas», que pode ser parafraseado por «um bife sem ter batatas fritas» ou «um bife sem vir acompanhado de batatas fritas».