Can an integer or rational sequence satisfy some bounded order recurrence $\mod \ $ almost all primes but doesn't satisfy such in $\mathbb{Q}$?


The recurrences $\mod p$ can be different, possibly depending on $p$ and the recurrence need not be linear, any recurrence will do.



Can an integer or rational sequence satisfy some bounded order recurrence $\mod \ $ almost all primes but doesn't satisfy such in $\mathbb{Q}$?
The answer to your question is NO. In fact, your hypothesis says that there is an infinite
set $\cal P$ of primes such that for each $p\in {\cal P}$ there is a function
$f\_p$ from ${\mathbb Z}\_p^r$ to ${\mathbb Z}\_p$ such that the sequence
$(a\_n)\_{n\geq 1}$ satisfies
$$ a\_{n+r+1} \equiv f\_p(a\_{n+1},a\_{n+2},a\_{n+3}, \ldots ,a\_{n+r}) \ ({\rm mod} \ p)$$
for all $n\geq 0$ and $p\in {\cal P}$.


Now consider the function $A$ defined by $A(n)=(a\_{n+1},a\_{n+2},a\_{n+3}, \ldots ,a\_{n+r})$ for all $n \geq 0$. If $A$ is injective, the sequence $(a\_n)\_{n\geq 1}$ satisfies a recurrence of degree $r$ in $\mathbb Q$. If $A$ is not injective, then there are integers 
$i \lt j$ such that $A(i)=A(j)$. Then the values $a\_{i+r+1}$ and $a\_{j+r+1}$ agree
modulo all primes in $\cal P$, and are therefore equal in $\mathbb Q$. By induction,
we see that the sequence $(a\_n)\_{n\geq 1}$ is eventually $(j-i)$-periodic. Then
a (more delicate) construction shows that $(a\_n)\_{n\geq 1}$ still satisfies a recurrence of degree $r$ in $\mathbb Q$


