First, let me offer some purely mathematical derivation, then we will attempt to address the storage problem once I get answers to the questions I posed in the comments above. I will edit this answer as needed.
Since $A$ is symmetric and positive definite, it admits a Cholesky factorization $A=LL^T$, where $L$ is lower triangular; and $A=L^{-T}L^{-1}$. Let us define $M=L^{-1}$, which is also a lower triangular matrix, so $A^{-1}=M^TM$; and let $m_k$ denote the $k$th column of $M$.
Furthermore, you say that $B$ is symmetric with two non-zero elements. This means that $B$ can take one of two forms:
$$B=\alpha(e_ie_j^T+e_je_i^T) \quad \text{or}\quad B=\alpha e_ie_i^T + \beta e_je_j^T$$
where $e_k$ is a vector with a one in the $k$th position and zeros elsewhere. Let's consider the first form for a moment:
$$\begin{aligned}
\mathop{\textrm{Tr}}(A^{-1}B)&=\alpha\mathop{\textrm{Tr}}(A^{-1}(e_ie_j^T+e_je_i^T))\\
&=\alpha\mathop{\textrm{Tr}}(A^{-1}e_ie_j^T)+\alpha\mathop{\textrm{Tr}}(A^{-1}e_je_i^T) \\
&=\alpha e_j^TA^{-1}e_i+\alpha e_i^TA^{-1}e_j = 2\alpha\left[A^{-1}\right]_{ij} \\
&= 2\alpha e_j^TM^TMe_i = 2\alpha \langle m_i,m_j \rangle
\end{aligned}
$$
So as you can see, the trace requires exactly one element of $A^{-1}$, or the inner product of two columns of $M$. A similar derivation for the second case yields
$$\mathop{\textrm{Tr}}(A^{-1}B)=\alpha\left[A^{-1}\right]_{ii}+\beta\left[A^{-1}\right]_{jj}+\alpha\langle m_i,m_i\rangle+\beta\langle m_j,m_j\rangle$$
So hopefully now it is clear why I asked: how many $B$ matrices are there? How is $A$ stored? What kinds of operations can we perform with $A$? Those questions are essential for determining what to do in this case. For instance, if there are only a handful of unique indices $i,j$ above, then one approach is to compute each $f_i\triangleq A^{-1}e_i$ using some sort of iterative method, then use $e_j^TA^{-1}e_I=e_j^Tf_i$.
But if most of the indices $i=1,2,\dots,10000$ are represented, it may be more expedient to do some sort of Cholesky factorization on the matrix. Yes, you may not have enough memory---to do an in-core factorization. But Cholesky factorizations can be done out-of-core. This involves performing the calculations in blocks, reading in only enough data into memory to solve that particular block, and writing each block to disk before proceeding with the next.
