I'd first make sure it's not CARP related (i.e. all packets always pass through one box), by (temporarily) turning off the backup box. If, for some reason, packets would flow through both boxes (some through the master, some through the backup), things would break in funny ways.
Now that everything must pass through the master, enable debug logging (pfctl -xm), note counters (pfctl -si), and reproduce the problem once. If you can, tcpdump one faulty connection (from the initial SYN to where the problem shows) on all relevant interfaces (two, I assume). Check /var/log/messages for lines from pf, especially "BAD state". Note updated counters (pfctl -si again), and diff old vs. new. Which counters are increasing? In your previous tcpdump, the client starts to use SACK after one packet from the server is lost. Maybe that is what distinguishes the clients (some use SACK, some don't). You could confirm this theory by (temporarily) disabling SACK on the server (net.inet.tcp.sack=0 on OpenBSD). Daniel