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:
Integral points on elliptic curves and explicit valuations of division polynomials, Katherine E. Stange, 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$.