In this paper, a distributed Telematics Peer-to-Peer (D-TP2P) networking system is proposed to provide an efficient and feasible service discovery mechanism for mobile clients. When mobile clients travel on the road, they may request for some services from service providers to meet their demands. Mobile users in vehicles are assumed to go through a lot of regions, in which each region is associated with a region server. Related information of all service providers in a region is stored in its region server and the region server is in charge of the service discovery requests from all vehicles located in its region. According to clients' demands, there are two types of search scenarios, which are (1) local search and (2) remote search. This paper focuses on the issues of developing a distributed P2P Telematics service discovery networking system over the vehicular network environment for mobile clients. A region server decision mechanism using a Safe-Zone Based Scheme (SZBS) is proposed to maintain correct connectivity between mobile clients and their associated region servers. A mobile client can have awareness of its region server and correctly send a request to its associated region server using SZBS. Then, the region server can help mobile users to find their requested service providers that are located locally or remotely. We also exhibit the performance merits of the proposed D-TP2P system in this paper. In the experiments, we showed that SZBS is better than the timer-triggered scheme.