A first Internet telephone system 620 attempts to call with a second Internet telephone system 630 via the Internet 600. However, the second Internet telephone system 630 is not logged onto the Internet at the time of the call. In response to the failed attempt to call, the first Internet telephone system prompts the user to send voice mail to the user of the second Internet telephone system. This results in a phone call over the Internet between a voice mail system 610 and the first Internet telephone system, allowing a greeting to be heard, and a message to be stored. This message may be subsequently retrieved, either using an Internet telephone system over the Internet, or using a standard phone over the conventional telephone network.