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.
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$
YES, define $a_k$ by $a_0=0$, $a_k=a_{-k}$ for $k<0$ and for $k>0$ $a_k=m!$ where $m\ge 1$ is as large as possible subject to $k$ being a multiple of $m!$. Then $$a_{k+m!} \equiv a_k \mod m.$$ However we have $a_j=a_{m\cdot m!+j}$ for $1 \le j\le m!-1$ but not for $j=m!$ when $a_{m!} \ne a_{(m+1)!}$ so the sequence can't satisfy a recurrence of finite order.
By request: Here it is from $a_{-9}$ to $a_{33}:$ $${\small \cdots 1,2,1,6,1,2,1,2,1,}\mathbf{0}\small{,\overline{1,2,1,2,1,6,1,2,1,2,1,6,1,2,1,2,1,6,1,2,1,2,1,24},1,2,1,2,1,6,1,\cdots}$$ $a_0=\mathbf{0}$ and all other terms are positive. The length 24 sequence with the overline keeps repeating except the $4!=24$ is $5!=120$ in positions 120,240,360,480,600 (but not 720) 840,960
Three notes:
This is not a new answer but a comment too long to fit in the usual comment format. It answers the "linear" variant of the problem suggested by Qiaochu. So let us suppose that there is an infinite set $\cal P$ of primes such that the sequence $(a_n)_{n\geq 1}$ satisifies some linear recurrence modulo $p$ for every $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$. Let $\Omega$ be the set of all integers $t\geq 1$ such that the vectors $A(i+1),A(i+2), \ldots ,A(i+t)$ are linearly dependent over $\mathbb Q$ for some $i$. Then $r+1\in \Omega$ so $\Omega$ is nonempty. Let $t$ be the smallest element in $\Omega$ , and pick up $i$ such that $A(i+1),A(i+2), \ldots ,A(i+t)$ are linearly dependent over $\mathbb Q$. By the choice of $t$, we have $t \leq r+1$ and $A(i+1),A(i+2), \ldots ,A(i+t-1)$ are linearly independent over $\mathbb Q$, so the last vector $A(i+t)$ is a linear combination of $A(i+1),A(i+2), \ldots ,A(i+t-1)$:
$$ (*) : A(i+t)=\sum_{k=1}^{t-1} \beta_k A(i+k)$$
for some coefficients $\beta_1,\beta_2, \ldots ,\beta_k \in {\mathbb Q}$. Now define a new sequence $(b_n)_{n \geq i}$ by
$$ b_n=a_{n+t}-\sum_{k=1}^{t-1} \beta_k a_{n+k}$$
By (*) above, the first $r$ values of $(b_n)_{n \geq 1}$ are $0$ (in $\mathbb Q$). Now for $p\in {\cal P}$, the sequence $(b_n \ ({\rm mod} \ p))_{n \geq i}$ satisifies a linear recurrence of order $r$, ans starts with $r$ zeroes. So that sequence is identically zero. We deduce that $p$ divides $b_n$ for any $p\in {\cal P}$ and $n \geq i$, so that $(b_n)_{n \geq i}$ is identically $0$ in $\mathbb Q$.
So we see that $(*)$ still holds when $i$ is replaced by any $n\geq i$, and that the initial sequence $(a_n)_{n\geq 1}$ eventually satisfies a linear recurrence of degree $\leq r$.
Ewan's answer works if you are assuming that the recurrence mod $p$ is of size at most $r$ for every $p$ in your set. It may be a different interpretation of the question than what you meant, but if you merely assume that the recurrences are finite mod $p$ (but no bound on how large the recurrence may be) but not finite over $\mathbb{Q}$, then the answer is yes, such a sequence does exist:
Let $p_n$ denote the $n^{th}$ prime and $p$# denote the product of all primes $\leq p$ and let $a_n$ be the following sequence:
$a_n = 0$ if $n<0$
$a_0$ = 1
$a_n$ = $\sum_{i=1}^\infty (p_i$#$)\cdot a_{n-i}$ if $n>0$
This sequence satisfies a $n^{th}$ order linear recurrence mod $p_n$ for every $n$ (since all but finitely many of the coefficients of the $\mathbb{Q}$-recurrence are 0 mod $p$), but does not satisfy any finite order recurrence over $\mathbb{Q}$.
I would guess that the answer is "yes", despite the apparent ill-posed nature of the query, simply because you can take a very rapidly growing sequence satisfying congruences modulo primes. In other words I'd expect some sort of growth condition to be required for any result at all here.
