Turns out it is possible to run out of moves in Blitz. It's not easy, it's not common, and Blitz really does seem to try and ensure that you have a move available at all times. But like any algorithm, it's not perfect.
It's happened to me at least four or five times since I posted this question. When you click the "hint" button, nothing will highlight -- that's because you're out of moves. Oddly, the game will not notify you that you're out of moves. My hunch is that because of the trouble they went through to prevent it from happening, they just didn't expect to ever encounter that issue. (But of course, I don't work for PopCap, so I'm just guessing there.)
When it happens, you have no choice but to either wait out the clock or restart the game.