It's not that they didn't believe, it's more likely that they believed that God has no obligation to actually participate in such a trail and went with a more controlled solution instead.
Wait, what? Assuming he exists (because otherwise the point is moot), are you saying that this God who created the UNIVERSE should be obligated to ask, "How high?" when we ask him to jump? Hinging one's belief (or disbelief) the existence of God on whether he is compliant with our wishes is foolishness; the mistake made by the priests here was NOT that they trusted in God (a neutral act in this example), but rather that they placed expectations of civil/criminal justice on a God who had promised them no such involvement in society. He didn't even provide this to the Israelites, with whom he had a much more intimate covenant. Instead, there were the judges/prophets/kings who administered justice.
What is more interesting to me is how these ordeals seem to (poorly) parallel the cut-the-baby-in-half sort of justice King Solomon was recorded to have administered. Except in his case it was obvious soon after that he never intended to carry out the sentence.
