Solution:

Let us denote $n=1000$. By the substitution $x=u+1$ and $y=v+1$ we obtain that the polynomial $u v-1$ divides the polynomial $P(u+1)+P(v+1)-(u+v+2)^{n}$. An equivalent condition is that $P(u+1)+P(v+1)-(u+v+2)^{n}=0$ whenever $u v-1=0$ (see remark). Thus for $u \neq 0$ and $v=\frac{1}{u}$ we have $P(u+1)+P\left(\frac{1}{u}+1\right)=\left(u+\frac{1}{u}+2\right)^{n}=\frac{(u+1)^{2 n}}{u^{n}}$. The polynomial $Q(x)=P(x+1)=\sum_{i=0}^{n} a_{i} x^{i}$ satisfies
$$2 a_{0}+\sum_{i=1}^{n} a_{i}\left(u^{i}+u^{-i}\right)=Q(u)+Q\left(\frac{1}{u}\right)=\frac{(u+1)^{2 n}}{u^{n}}=\binom{2 n}{n}+\sum_{i=1}^{n}\binom{2 n}{n-i}\left(u^{i}+u^{-i}\right)$$
from which it immediately follows that $a_{0}=\frac{1}{2}\binom{2 n}{n}$ and $a_{i}=\binom{2 n}{n-i}$ for $1 \leqslant i \leqslant n$. Hence,
$$P(x)=\frac{1}{2}\binom{2 n}{n}+\sum_{i=1}^{n}\binom{2 n}{n-i}(x-1)^{i}$$

Second solution. We seek polynomials $P(x)=\sum_{i=0}^{n} p_{i} x^{i}$ and $Q(x, y)=\sum_{i, j} a_{i, j} x^{i} y^{j}$ such that
$$A(x, y)=(x y-x-y) Q(x, y)=(x+y)^{1000}-P(x)-P(y)$$
Notice that $\operatorname{deg} Q \leqslant 998$. Indeed, if $a_{i, j} x^{i} y^{j}$ is the monomial of highest degree in $Q(x, y)$, then the coefficient of $x^{i+1} y^{j+1}$ in $A(x, y)$ equals $a_{i, j} \neq 0$, so $i+j+2 \leqslant 1000$. It follows that $\operatorname{deg} A \leqslant 1000$, hence also $\operatorname{deg} P \leqslant 1000$.
Equating the coefficients of $x^{i} y^{j}$ in (*) gives the equalities $a_{i-1, j-1}=\binom{1000}{i}$ for $i+j=998(i, j>0), a_{i-1, j-1}=a_{i-1, j}+a_{i, j-1}$ for $i+j<998(i, j>0)$ and $a_{i-1,0}=$ $a_{0, i-1}=p_{i}$, from which by simple induction we find $a_{i-1, j-1}=\binom{2000-i-j}{1000-i}$ for $i+j \leqslant 1000(i, j>0)$ and $p_{i}=\binom{1999-i}{999}$, i.e.,
$$P(x)=x^{1000}+\binom{1000}{999} x^{999}+\binom{1001}{999} x^{998}+\cdots+\binom{1998}{999} x$$

Third solution. There do not exist two distinct polynomials with the desired property. Indeed, if $P_{1}(x) \not \equiv P_{2}(x)$ have this property, then $x y-x-y$ divides the difference $P_{1}(x)+P_{1}(y)-P_{2}(x)-P_{2}(y)=(x y-x-y) U(x, y)$. However, if $c x^{i} y^{j}$ is the monomial of highest degree in $U(x, y)$, then the coefficient of $x^{i+1} y^{j+1}$ on the left-hand side of this equality equals $c \neq 0$, which is impossible.
Let us now prove that for every symmetric polynomial $Q(x, y)$ there exists a polynomial $P(t)$ such that $x y-x-y \mid Q(x, y)-P(x)-P(y)$. It suffices to prove that for polynomials $Q$ of the form $x^{i} y^{j}+x^{j} y^{i}(0 \leqslant i \leqslant j)$ there exists the required polynomial $P_{i, j}(t)$. The claim is trivial for $i=0$. For $i>0$ we carry out the proof by induction on $i+j$. Namely, $x^{i} y^{j}+x^{j} y^{i} \equiv(x+y)\left(x^{i-1} y^{j-1}+x^{j-1} y^{i-1}\right)=\left(x^{i} y^{j-1}+x^{j-1} y^{i}\right)+$ $\left(x^{i-1} y^{j}+x^{j} y^{i-1}\right)(\bmod x y-x-y)$, so we can take $P_{i, j}(t)=P_{i, j-1}(t)+P_{i-1, j}(t)$.