The configurations in 3-dimensional case are called ovoids: en.wikipedia.org/wiki/Ovoid_%28projective_geometry%29

And there is a new easy proof of that lower bound using a result of Alon and Füredi, along with a nice generalisation: arxiv.org/abs/1404.7793

(contd ...) A particular case of this, where each $S_i = \mathbb{F}_q$, and you are looking at polynomials over $\mathbb{F}_q$ was already proved in this paper by Bruen, sciencedirect.com/science/article/pii/009731659290035S, by more or less similar arguments.

It's probably worthwhile to note that one can easily avoid CN in Example 3. Basically, you want to prove that any polynomial that vanishes on all points of a grid $S_1 \times \cdots \times S_n$ except one must have degree at least $\sum |S_i| - 1$. This can be proved by induction on $\sum |S_i| - 1$. For a particular case of this, see my solution here: artofproblemsolving.com/wiki/index.php/2007_IMO_Problems/…. (contd ...)

There are in fact many other proofs that can be given of this weak form, all relying on a crucial Lemma about polynomials vanishing on all points but one. See my answer: mathoverflow.net/a/202398/34180