Thanks Danpost! I found the bug. When the AI checked the Queen's movement possibilities to the right, it found the pawn, checked to see what happens if it captured it, finds out its King is still in check, so continued with path. The execution break for the path (to the right), when it found a piece (the pawn) occurred after the king check, so was skipped.

If that is not the case, then if you have the Jave Console open next time it happens, copy the printed move history of that game so I can reproduce the problem.