I have a feeling someone smarter than me will provide an answer with better references, but I still hope this answer helps.

Not long ago I was out on a walking tour of Aoyama Cemetary and the exact same question came up. The tour guide, who has studied religion and history offered this explanation (and was backed up by a Japanese guy, but I don't know his credentials):

無い　（な・い) means a complete absence of anything, which I think in English we would equate with void, so it would seem like the right choice.

空　（そら） means an emptiness as well, however, and was used to refer to the air from back before the more modern and scientific concept that the air is not in fact emtpy but contains molecules.

The difference between them is that the emptiness referred to by 空 is, as our guide explained, like the emptiness inside a cup. It is empty, but is conceptually bounded by the cup so that it is a space that could hold something, such as a drink.

無い on the other hand means a complete absence, without even any implication of potential. In other words, no cup.

In the Bhuddist use, then, when you see it on the top layer of the five elements, ([地,水、火、風、空][1], earth, water, fire, air, void), implies an emptiness that has a potential to contain something.

Of course, it gets a little tricky because there is no "cup" for the concept of all of existence. The void being referred to by 空 doesn't imply that anything particular should occupy that space. There is no automatic equivelent for the universe to hold like a drink would seem to be the natural thing to fill a cup. Just that the void is a vessel into which existence can happen. And from here the philosophical discussion takes over from the linguistic one.

Side note: 風　（かぜ）, or wind, in this context actually means "air", as back in the day, the "air" was only experienced when you could feel the wind. Before I had this discussion on the tour, I always thought they were simply differentiating wind from air.


  [1]: http://upload.wikimedia.org/wikipedia/commons/7/76/Pagoda.svg