Actually, the binary linear recurrence case is pretty precise, especially if $p\ge3$ and you're working over $\mathbb Q$, and not over a field where $p$ is ramified. Let $r(p)$ denote the rank of apparition, which is the smallest $r$ such that $p\mid a_r$. Then if $p\ge3$, we have
$$ \text{ord}_p(a_n) = \begin{cases}
       0 &\text{if $r(p)\nmid n$,} \\
       \text{ord}_p(a_{r(p)}) + \text{ord}_p(n/r(p)) &\text{if $r(p)\mid n$.} \\
  \end{cases}
$$
In the literature there are sources which state this as a theorem for all primes in all number fields, but it's not quite right for $p=2$ over $\mathbb Q$, nor for larger $p$ if $p$ is ramified. The best source that I know for the general result is:


Stange, Katherine E.,
Integral points on elliptic curves and explicit valuations of division polynomials. 
*Canad. J. Math.* **68** (2016), no. 5, 1120-1158. (MR3536930) http://arxiv.org/abs/1108.3051

The case of $p\ge3$ over $\mathbb Q$ is a fairly easy exercise once one understands that underlying these binary linear recurrences (and also underlying elliptic divisibility sequences) is a one-dimensional algebraic group, and the desired result follows from a calculation in the formal group.

On the other hand, it is a very hard (pretty much open) problem to determine if there are infinitely many $n$ such that $\text{ord}_p(a_{r(p)})\ge2$, or even that there are infinitely many $n$ such that $\text{ord}_p(a_{r(p)})=1$, although presumably the latter occurs for almost all $n$. Both problems are open even for $a_n=2^n-1$.