Methods, systems, and computer readable media for regulating pinhole preservation traffic generated or received by firewall or network address translator (NAT) session initiation protocol (SIP) user agent clients (UACs) are disclosed. One method includes, maintaining a list of contact information for a plurality of SIP UACs registering from behind at least one of a firewall and a NAT. The method further includes iterating through the list to generate SIP messages to the different UACs such that the SIP messages to the different UACs are spaced at substantially regular intervals with respect to each other, wherein the SIP messages to the different UACs trigger responses from the UACs such that the responses are spaced at substantially regular intervals with respect each other.