Methods and apparatus for implementing communication services such as voice dialing services are described. In one Centrex based voice dialing embodiment, voice dialing service subscribers are given access to personal voice dialing records including calling entries via the Internet as well as via telephone connections. Each calling entry normally includes the name and, optionally nickname, of a party to be called. It also includes one or more telephone numbers associated with each name. Different telephone number identifies, e.g. locations, can be associated with different names. A user can create or update entries in a voice dialing directory using text conveyed over the Internet or speech supplied via a telephone connection. In order to facilitate updating and maintenance of voice dialing directories over the Internet speaker independent (SI) speech recognition models are used. When a calling entry is created via the Internet the text of the name is processed to generate a corresponding speech recognition model there from. When an entry is created via speech obtained over the telephone, a speech recognition model is generated from the speech and a text name is generated is generated using speech to text technology. To avoid having to hang-up and initiate a new voice dialing call the outcome of a voice dialing call is monitored and the subscriber is provided the opportunity to initiate another call using voice dialing if the first call did not complete successfully e.g., goes unanswered.