You are assuming that order doesn't matter in the second case, but this is the wrong assumption. Order definitely matters. You have, in the case of $n=6$ a sample space of $6^2$ Even though when you finally pull both tags out, a $(2,1)$ is the same as $(1,2)$, these are still different events and must be treated differently. Since this is the case, let's look at $n=6$. All consecutive numbers then would be;
$$(1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,4),(5,6),(6,5)$$
So here you have 10 events that are possible, not 5. And your sample space is 36... Therefore, your probability is
$$\frac{10}{36}=\frac{2\cdot5}{6^2}=\frac{2(6-1)}{6^2}$$
And this makes sense. You can only have $n-1$ consecutive pairs, since the $n$-th pair would be $(n,1)$ which are not consecutive, and our sample space consists of $n^2$ events. Since there are two ways to get consecutive integers, the formula is
$$P(\text{consecutive numbers with replacement of n tags})=\frac{2(n-1)}{n^2}$$
Also, in the first case, again, you are making the faulty assumption that $(1,2)$ is the same as $(2,1)$ and I think that you make this assumption because the probability is correct under both assumptions, i.e., yours, and the correct assumption. Why?
The sample space under sampling without replacement is in the case of $n=6$ is $6\cdot5=30$. This is the case because pairs such as $(1,1), (2,2)$ are impossible without replacement. However, you can still get the ten pairs of consecutive numbers listed above, so therefore, under the correct assumption
$$P(\text{consecutive numbers without replacement of n tags})=\frac{2(n-1)}{n(n-1)}=\frac2{n}$$
If $n=6$, you get your probability is $\frac1{3}$, which is what you got under your faulty assumption. Hope this helps shed a little light.
For $n$ people, the probability is $$\left(1-\frac1n\right)^n\approx \frac1e$$
To explain that, notice that the natural logarithm of $1+x$ is close to $x$ when $x$ is small. (Try it for $\ln(1.1),\ln(1.01),\ln(1.001)$).
So the log of the left-hand side is $n\log(1-\frac1n)\approx(n(-\frac1n))=-1$.
Since the log is near $-1$, the probability is near $1/e$.
Best Answer
It's often easier to calculate the complement event and then do 1- that. Here the complement event is that no two numbers are equal.
The first number is arbitrary, so there is no chance of it being duplicated, or 1000/1000
The second number has 999/1000 chance of being different from the first number
Continuing onwards, we get $$\frac {1000P40} {1000^{40}}$$ ways of picking 4 numbers
Doing the compliment, $$1-\frac {1000P40} {1000^{40}}$$ gets us via wolframalpha to roughly $54.64\%$, which meshes well with your experimental data