Depends on the size of the network I would guess. A Boltzmann brain would apparently take about 10^10^50 years to form from quantum fluctuation in a vacuum. Our hypothetical neural network would be less complicated than that, assuming we're not aiming for general AI, so I think we can safely take that as an upper bound...

With a uniform initialization, presumably you'd never need much more than 2^(network bit complexity) number of samples to come across an ideally-initialized network with decent probability, so that's 2^10^24 for anything that fits in a yottabyte.

In the absence of dynamics and uniform random mutation, yes. But Both don't hold in the universe.

Surprisingly, it's quite doable in practice. See e.g. https://arxiv.org/abs/1911.13299.