Not a direct answer, but too long for a comment, I think.
A first step in thinking about this question is: what are some procedures which always either: 1) solve the dollar game, or 2) show the dollar game is not solvable for the given configuration.
For convenience, assume we are working with a (connected) undirected graph; things get more complicated with directed graphs.
In the Riemann-Roch context, Baker and Norine developed the following algorithm for this problem. First, choose an arbitrary "sink vertex" $q$. The sink vertex serves as the "bank" or "government" and goes heavily into debt, firing many many times to give all its neighbors a lot of chips, and then the neighbors spread their excess chips to their neighbors, and so on, and it's easy to see that (since the graph is connected) by making $q$ very negative we can make everyone else positive. Then, we try to get $q$ itself out of debt, and the way we do this is to "superstabilize" the non-sink vertices: this means we repeatedly look for nonempty subsets of the non-sink vertices that have more chips than edges leaving the subset, and we fire such subsets as long as we can. If this superstabilization process leaves $q$ with a nonnegative number of chips, then we win; otherwise the game was not winnable. Note that checking whether a configuration (on the non-sink vertices) is superstable a priori involves exponentially many checks (we have to consider all subsets), but in fact Dhar's burning algorithm gives a linear time algorithm for checking superstability.
So that's one way to win the dollar game, but actually via the "dual" process I hinted about in the comments above, the original Björner, Lovasz, and Shor paper gives a completely different way for winning the dollar game. Namely, repeatedly have vertices with a negative number of chips borrow a chip from all their neighbors. If you don't want to allow borrowing moves, then note that a vertex borrowing from all its neighbors is the same as all the other vertices firing. If the game is winnable, then having repeatedly vertices with a negative number of chips borrow a chip from all their neighbors will win the game. If the game is not winnable, then eventually every vertex will try to borrow in this way. So we know to stop, and that the game is not winnable, if every vertex tries to borrow.
So, we have two pretty different strategies for always winning the dollar game. Of course, there is no guarantee that either of these strategies is always the 'fastest' one for winning. But giving (upper) bounds for the time taken by these strategies evidently gives bounds for the best strategy. And as mentioned in comments above, at least for the 2nd strategy many things are known with respect to time bounds (e.g. there is a polynomial bound).
