A media session is established between a first device (e.g., endpoint) and a second device (e.g., endpoint) via a communication network based on connectivity checks performed by the devices. A set of candidate pairs, including network addresses available to the first device and the second device, is generated. Among the candidate pairs of the candidate pair set, a respective priority is initially assigned for connectivity checks. If a connectivity check modification condition is determined to be met for candidate pairs used for connectivity checks, the priority ordering of the candidate pairs is modified to produce a second priority ordering. This second priority ordering assigns a higher priority for a candidate pair which meets the connectivity check modification condition than a candidate pair that does not meet the condition. Based on the modified ordering, connectivity checks are performed, and the media session is configured and established using a candidate pair determined to be valid.