I still don't have a full solution, but I was able to solve a much larger number of test cases once I realized a condition that was only slightly implied by the problem description.

It says, "the goal of the game is to capture the opponent’s Queen without losing your own."

When I first read that the algorithm should "determine whether or not White can win in <= m moves regardless of how Black plays," I thought the algorithm didn't need to take into account any strategy. However, my code was incorrect until I implemented some logic that ensures a player will (1) never make a move that puts his queen in danger, and (2) always take his queen out of danger if possible.

Maybe this was obvious, but it took me a long time before I realized this. Hopefully it helps someone else.