I was initially wondering about this too.

Actually, I was thinking about it the other way around: that maybe Harry had to make sure not only that he arrived earlier than the time he recorded so he'd be there for Minerva to find, but also that he arrived after the time of the communication to avoid there being two Harrys for the Patronus to find.

But putting it that way made me realize that no, clearly that isn't a problem: the Patronus (did/does) find the Harry in Azkaban, regardless of what else might be true.

As you point out, we don't know how it did so... maybe it flipped a glowing animal-headed coin... but we know it did so, by observation, and Harry does too.