The following is an incomplete answer.
The challenge from relaxing the "always halts" condition to "almost surely halts" is that the graph of configurations is now allowed to have cycles. A consequence is that if you take polynomially many steps, the probability of halting may be exponentially small. For example, you can have a counter which, with probability $\frac{1}{2}$, either increments by one or resets to zero. That counter will reach $N$ in $N$ steps with probability $\frac{1}{2^N}$.
Remark that this is a lower bound: if there are $c$ configurations, you will reach a halting state within $c$ steps with probability at least $\frac{1}{2^c}$. This is because from every reachable configuration, you must get closer to a halting state with probability at least $\frac{1}{2}$.
Consequently, if we want to approximate the probability of accept vs reject to a reasonable degree, it is sufficient to exponentiate the transition matrix $M$ exponentially many times, $2^{\mathcal{O}(c)}$, where $c$ is the number of configurations. This is feasible in $\mathcal{O}(c)$ matrix multiplications thanks to fast exponentiation. The remaining obstacle is that the size of the scalars grows exponentially.
That's where I don't know how to conclude, but one idea is that maybe we don't need to compute the probability to exact precision. If we can show that truncating probabilities to a polynomial number of bits doesn't lose too much precision, then we can compute an approximation of $M^{2^{\mathcal{O}(c)}}$ in polynomial time.
