The answer is that 1000 is the only possibility. Here is an ugly way of writing the proof of this: We have a list of 2000 numbers which contains every number from 0 to 1999 once, except that one number is missing and one number is included twice. It is inconsistent to have both a 0 and a 1999, so one of these must be missing. Suppose first that 0 is absent and that 1999 is represented. We will construct the graph recursively: choose a vertex to be the vertex of degree 1999. (There cannot be two vertices of degree 1999, or there would be no vertices of degree 1, and that would be bad.) Then among the other 1999 vertices, one must be the vertex of degree 1, and it has its edge already. (If there were two vertices of degree 1, the maximal possible degree would have been 1997, i.e. we would have no vertex of degree 1998, and that would be bad.) So among the remaining 1998 vertices, the maximal possible degree is 1998, and it must be connected to each of the not-yet-considered vertices. (And again, there can only be one of these.) We must have a vertex of degree 2 among these, so we have exhausted its edges. (And it must be unique.) Then among the remaining 1996 vertices, the maximal possible degree is 1997, and that vertex must be unique, and so on. Finally, we have found a vertex of degree 1, 2, 3, ..., 998, 1001, 1002, ..., 1999. We have not yet considered 3 vertices, and they currently have degree 999. Only one of them must be the vertex of degree 999 (and there cannot be more than 1, or else there would be no vertex of degree 1000). So the other two vertices must be connected to each other, and they must have degree 1000. Has this question appeared on the forum or some other contest before? It feels vaguely familiar.

Sorry to revive this, but I'm going through some old Tuymaada problems, and the only solver here is unhappy about his effort, and he has missed a finer point of the problem. Of course it is a familiar problem - its usual formulation uses handshakes. Let us introduce induction where induction seems not to be, and consider a graph on $2n$ vertices, such that exactly two degrees of vertices are equal. We claim the common value of those two equal degrees can only be $n$ (when there is no $0$ degree vertex, but there is a $2n-1$ degree vertex) or $n-1$ (when there is no $2n-1$ degree vertex, but there is a $0$ degree vertex). Clearly, each of these two cases on a graph $G$ corresponds to the other on the complementary graph $\overline{G}$. For $n=1$, this is trivial; either we have the one possible edge, or we don't. For $n>1$, notice, as above, that one cannot have both a $0$ and a $2n-1$ degree vertex. Say there is a $2n-1$ degree vertex, so there also is a $1$ degree vertex. Notice, as above, that the $2n-1$ degree cannot be duplicated, and neither the $1$ degree. Remove these two vertices; we are left with a graph on $2(n-1)$ vertices, each of degree one less than before, so having the same property of exactly one degree duplicated. Apply the induction hypothesis; since this graph has no $0$ degree vertex, its duplicated degree must be $n-1$, so that of the original graph was $n$. Say there is a $0$ vertex. The complementary graph has a $2n-1$ degree vertex, so we may apply the above. Then the duplicated degree in the original graph is $(2n-1) - n = n-1$, and we are completely done.