(1) Obviously the number of the values of $S$ is finite, so the maximum and minimum exist. Suppose $x_1 + x_2 + x_3 + x_4 + x_5 = 2006$ such that $S = \sum_{1 \le i < j \le 5} x_i x_j$ reaches the maximum, we must have
$$|x_i - x_j| \le 1, \quad (1 \le i, j \le 5).$$
Otherwise, assume that this does not hold. Without loss of generality, suppose $x_1 - x_2 \ge 2$. Let $x_1' = x_1 - 1$, $x_2' = x_2 + 1$, $x_i' = x_i$ ($i = 3, 4, 5$). We have
$$\begin{aligned} x_1' + x_2' + x_3' + x_4' + x_5' &= x_1 + x_2 + x_3 + x_4 + x_5 \\ &= 2006, \end{aligned}$$
$$S = \sum_{1 \le i < j \le 5} x_i x_j = x_1 x_2 + (x_1 + x_2)(x_3 + x_4 + x_5) + x_3 x_4 + x_3 x_5 + x_4 x_5,$$
$$S' = x_1' x_2' + (x_1' + x_2')(x_3 + x_4 + x_5) + x_3 x_4 + x_3 x_5 + x_4 x_5.$$
So
$$S' - S = x_1' x_2' - x_1 x_2 > 0.$$
This contradicts the assumption that $S$ is the maximum.
Therefore $|x_i - x_j| \le 1$ for $1 \le i, j \le 5$. And it is easy to check that $S$ reaches the maximum when
$$x_1 = 402, \quad x_2 = x_3 = x_4 = x_5 = 401.$$

(2) If we neglect the order in $x_1, x_2, x_3, x_4, x_5$, there could only be three cases:
(a) $402, 402, 402, 400, 400$;
(b) $402, 402, 401, 401, 400$;
(c) $402, 401, 401, 401, 401$.
That satisfy $x_1 + x_2 + x_3 + x_4 + x_5 = 2006$ and $|x_i - x_j| \le 2$.
Cases (b) and (c) can be obtained from Case (a) by setting $x_i' = x_i - 1$, $x_j' = x_j + 1$. What we have done in (1) tells us that each step like this will make $S' = \sum_{1 \le i < j \le 5} x_i' x_j'$ greater. So $S$ is the minimum in Case (a), i.e. $x_1 = x_2 = x_3 = 402$, $x_4 = x_5 = 400$.