A system and method of instant messaging is provided. A plurality of messaging clients capable of transmitting instant messages to one another are each configured to share presence information with one another via a network. A determination is made, with respect to each of the messaging clients, as to whether the messaging client is in a state in which it is receptive to receiving presence information from the other messaging clients, and if so, then the presence information is provided to the messaging client. The presence information may be provided directly between the messaging clients, or it may be provided through one or more centralized proxy servers that store and propagate the presence information. A special state is provided, referred to herein as the unknown state, which when entered by a particular messaging client will cause the system to cease further transmissions of presence information to that client and/or transmissions about that client. Upon changing to a communicative state, the system resumes providing presence information to/about the messaging client.