The present invention relates to communications methods and apparatus for distributing Session Initiation Protocol (SIP) messages among SIP processing entities including during periods of failure recovery. An exemplary method embodiment includes the steps of: establishing a first connection oriented protocol connection between a first Session Initiation Protocol Load Balancer (SLB) of a plurality of SLBs and a client device; receiving via the first connection oriented protocol connection at the first SLB a first SIP REGISTER request message from the first client device; determining, by the first SLB, based on information received from the client device, a first Session Border Controller (SBC) from a plurality of SBCs to send the first SIP REGISTER request message, said information uniquely identifying the first SBC from other SBCs in the plurality of SBCs; and sending, by the first SLB, the first SIP REGISTER request message to the first SBC.