Methods and apparatus to route emergency communication sessions are disclosed. An example method involves querying a gateway node cache in response to a first broadcast probe received at a node of a wireless Internet-based network. When the gateway node cache identifies a first gateway node, a first response is selectively sent to nodes that participated in a search flood associated with the first broadcast probe.