Cesko-Slovacko-Poljsko, 2006

Every sequence satisfying given conditions is determined by first two terms. Thus we are looking for integer pairs $(a_1, a_2)$, for which all the other terms are integers. Writing out the formula for several small values of $n$ and multiplying it we obtain
$$\begin{align*} a_3(a_2 + 1) &= a_1 + 2006, \\ a_4(a_3 + 1) &= a_2 + 2006, \\ a_5(a_4 + 1) &= a_3 + 2006, \end{align*}$$
Subtracting adjacent equalities (to remove number 2006) and rearranging gives
$$\begin{align*} a_3 - a_1 &= (a_3 + 1)(a_4 - a_2), \\ a_4 - a_2 &= (a_4 + 1)(a_5 - a_3), \\ a_5 - a_3 &= (a_5 + 1)(a_6 - a_4), \end{align*} \tag{1}$$

All the terms $(a_n + 1)$ are nonzero by definition. Hence two possibilities can happen. If $a_3 - a_1 = 0$, by substituting into previous we get (step by step) $a_4 - a_2 = 0$, $a_5 - a_3 = 0$, ..., i.e.
$$a_1 = a_3 = a_5 = \dots \quad \text{and} \quad a_2 = a_4 = a_6 = \dots \qquad (2)$$
On the other side, if $a_3 - a_1 \neq 0$, by the same substituting we obtain $a_4 - a_2 \neq 0$, $a_5 - a_3 \neq 0$, ... First have a look at the second case. By (1) we have
$$0 < |a_{n+3} - a_{n+1}| = |a_{n+2} - a_n| \cdot \frac{1}{|a_{n+2} + 1|} \le |a_{n+2} - a_n| \qquad (3)$$
for all $n \ge 1$. Thus we have non-increasing sequence of positive integers
$$|a_3 - a_1| \ge |a_4 - a_2| \ge |a_5 - a_3| \ge \dots$$
Obviously this sequence is constant after some term (otherwise we could select infinite decreasing subsequence of positive integers, which is anyway impossible). Thus there is some index $N$ and value $d$ with $|a_{n+2} - a_n| = d$ for all $n \ge N$. By (3) then $|a_{n+2} + 1| = 1$, i.e. for $n \ge N+2$ we have $a_n \in \{0, -2\}$. But by definition
$$a_{N+4} = \frac{a_{N+2} + 2006}{a_{N+3} + 1},$$
hence $a_{N+4}$ is one of the values
$$\frac{0+2006}{0+1} = 2006, \quad \frac{0+2006}{-2+1} = -2006, \quad \frac{-2+2006}{0+1} = 2004, \quad \frac{-2+2006}{-2+1} = -2004.$$
This is in contrary with $a_{N+4} \in \{0, -2\}$. In this case there is no sequence satisfying given conditions. Therefore every such sequence satisfies (2). Substituting $n=1$ and $a_3 = a_1$ in definition we get
$$a_1 = \frac{a_1 + 2006}{a_2 + 1} \quad \text{or} \quad a_1 a_2 = 2006 = 2 \cdot 17 \cdot 59.$$
Considering $a_1, a_2 \neq -1$ we obtain
$$a_1 \in \{1, \pm 2, \pm 17, \pm 34, \pm 59, \pm 118, \pm 1003, 2006\} \quad \text{and} \quad a_2 = \frac{2006}{a_1}.$$
It can be easily verified every such sequence $a_1, a_2, a_3, a_4, a_5, \dots$ satisfies given condition. The number of sequences is 14.