for 768 dimensions, you'd still expect to hit (1-1/N) with a few billion samples though. Like that's a 1/N of 0.13%, which quite frankly isn't that rare at all?
Of course are vectors are not only points in one coordinate axes, but it still isn't that small compared to billions of samples.
Bear in mind that these are not base vectors at this stage (which would indeed give you 1/768). They are arbitrary linear combinations. There are exponentially many near orthogonal of these vectors for small epsilon. And epsilon is chosen pretty small in the paper.
Of course are vectors are not only points in one coordinate axes, but it still isn't that small compared to billions of samples.