Given that $k$ and $a$ are positive integers, and $2004k + a$, $2004(k+1) + a$ are both perfect squares.

(1) How many ordered pairs of positive integers $(k, a)$ are there?
(2) Identify the minimum value of $a$ and explain your reasoning.
II. (1) Let $2004k + a = m^2$,
(1)
$$
2004(k+1) + a = n^2 \text{, }
$$

where $m, n$ are positive integers, then
$$
n^2 - m^2 = 2004 \text{. }
$$

Thus, $(n+m)(n-m) = 2004 = 2 \times 2 \times 3 \times 167$.
Noting that $m+n$ and $n-m$ have the same parity, we have
$$
\left\{\begin{array}{l}
n + m = 1002, \\
n - m = 2
\end{array} \text{ or } \left\{\begin{array}{l}
n + m = 334, \\
n - m = 6
\end{array}\right.\right.
$$

Solving these, we get $\left\{\begin{array}{l}n=502, \\ m=500\end{array}\right.$ or $\left\{\begin{array}{l}n=170, \\ m=164\end{array}\right.$
When $n=502, m=500$, from equation (1) we have
$$
2004k + a = 250000 \text{. }
$$

Thus, $a = 2004(124 - k) + 1504$.
Since $k$ and $a$ are positive integers, $k$ can take values $1, 2, \cdots, 124$, resulting in 124 pairs of positive integer solutions $(k, a)$.
When $n=170, m=164$, from equation (1) we have
$2004k + a = 26896$.
Thus, $a = 2004(13 - k) + 844$.
Since $k$ and $a$ are positive integers, $k$ can take values $1, 2, \cdots, 13$, resulting in 13 pairs of positive integer solutions $(k, a)$.
Therefore, the total number of positive integer solutions $(k, a)$ is $124 + 13 = 137$ (pairs).
(2) The smallest positive integer $a$ satisfying equation (3) is 1504. The smallest positive integer $a$ satisfying equation (4) is 844.
Thus, the smallest value of $a$ is 844.