Let me start off by saying that I'm not a mathematician, so this is probably an easy problem to solve, but I haven't been able to yet..
The problem is that I want to place $n$ objects on a grid with $N$ grid points, and I want to count the number of different permutations this is possible, or at the least an approximate number. However, I am not allowed to place my objects just next to others, and therefore the number of possible places to place them, decreases by a number $s$ after having placed an object.
You can see here, how the situation works for a 4x4 grid with $n=1$ (gives $\binom{4\times 4}{1}=16$ possibilities since no grid points are masked out) and for $n=2$ where one grid point is occupied - removing the option to use its neighboring grid points.
Having placed a single object, the number of grid points available are not $16-1=15$, but rather $16-9=7$. Therefore, the total number of permutations goes from $\binom{16}{2}=16\times 15 / 2 = 120$ to $16\times 7/2=56$. Here I showed it with periodic boundaries as this is preferred, but it is not necessary.
I guess the binomial coefficient $\binom{N}{n}$ is a good starting place, as this can give the number of permutations for a static size grid, however, I haven't been able to figure out how to find it for a non-static $N$.
I thought I could get an approximate answer by just calculating $$ \prod_{i=0}^n N-i\cdot s $$ but this obviously double counts a lot of the same configurations.
Some thoughts toward an answer.
I think you are closer to an estimate than you think you are - your original idea is on the right track.
The problem with periodic boundary conditions (so placing your points on a torus) is in fact easier.
In your example you work with the requirement that points can't be immediate neighbors - they can share neither an edge nor a corner. Suppose too that $n << N$ and that the points are placed more or less at random, subject to the neighbor restriction. Then it's unlikely that the restricted areas from two points will overlap. That means that each point placed rules out $25$ vertices on the grid - the spot the point is on, its $8$ neighbors, and their neighbors too. So when $k$ points have been placed the next point can go in any of the remaining $N-25k$ places. That leads to the product in your question: $$ N(N-25)(N-50) \cdots (N- 25(n-1)). $$ But the order in which you placed the points doesn't matter, so to find the number of arrangements just divide that product by $n!$. That deals with what you call the double counting - you take care of it at the end all at once rather than by using binomial coefficients along the way.
There will be legal placements that aren't counted here, because two points could be two steps apart without conflict. That will matter more the closer $n$ is to the maximum number that will fit. If your application sprinkles fewer points in a larger grid this will give you a reasonable lower bound for the number of configurations.