Solution:

The answer is 042. Let $q(x)=p(x)-2 x$. Since $p(k)=2 k$ for $k=1, \ldots, 20$, then also $q(k)=0$ for $k=1, \ldots, 20$. By the Factor Theorem, this is equivalent to saying that the polynomial $q(x)$ is divisible by $x-1, x-2, \ldots, x-20$. But then it is also divisible by their product, and hence we have
$$q(x)=(x-1)(x-2) \cdots(x-20) r(x)$$
for some polynomial $r(x)$. If $r(x)$ had degree 1 or higher, $q(x)$ and hence also $p(x)=q(x)+2 x$ would come to have degree higher than 20, which contradicts the hypothesis. So $r(x)$ is constant, say $r(x)=\alpha$. Expanding the product in equation (2) we then get that the term of maximum degree (that is, 20) of $q(x)$, and hence of $p(x)$, has coefficient $\alpha$; hence it must be $r(x)=\alpha=1$. We have thus shown that
$$q(x)=(x-1)(x-2) \cdots(x-20) .$$
From this equality it follows that
$$p(x)=(x-1)(x-2) \cdots(x-20)+2 x$$
and hence, evaluating the polynomial at $x=21$, we get
$$p(21)=20 \cdot 19 \cdots 1+2 \cdot 21=20 !+42$$
The term 20! is a multiple of 1000 (one can easily verify that it contains enough factors of 2 and 5); more precisely, 20! ends with exactly 4 zeros (there are only 4 factors equal to 5). Hence the last three digits of $p(21)$ are 042.