I tried out 1v1v1 and 1v1v1v1 skirmishes for the first time today, and each time the stalemate screen came up less than 30 seconds into the battle. I later played 1v1 and 2v2, and they both worked fine.
Is the stalemate screen a new thing, by the way? I've never seen it before today.