1. At a messaging server configured to deliver messages to message inboxes, the messaging server including a processor and system memory, the messaging server in a messaging system network that includes a plurality of forests corresponding to a plurality of domains, wherein each forest stores a plurality of message inboxes for a corresponding plurality of e-mail message recipients, and wherein no unified directory maps a particular forest as a forest that stores a particular message inbox corresponding to where a particular recipient receives e-mail messages, the messaging server configured to receive e-mail messages addressed within the plurality of domains and to deliver the received e-mail messages to particular forests that store particular message inboxes corresponding to the e-mail messages, a computer implemented method of delivering an e-mail message to a forest that stores a particular message inbox corresponding to where a particular recipient receives e-mail messages, the computer implemented method comprising acts of: receiving an e-mail message, the e-mail message addressed to the particular recipient at a destination address, the destination address comprising a user name portion and a domain name portion, wherein the destination address is ambiguous such that at least the domain name portion identifies the messaging server, but does not uniquely identify any particular domain corresponding to a particular forest from among the plurality of forests that stores the particular message inbox corresponding to where the particular recipient receives e-mail messages; sending a recipient inquiry using an e-mail message protocol to a first forest from among the plurality of forests, the first forest storing a subset of the plurality of message inboxes for a corresponding subset of the plurality of message recipients, the recipient inquiry sending at least the user name portion of the destination address and inquiring whether or not the first forest is a forest that stores the particular a candidate message inbox corresponding to where the particular recipient having the user name receives e-mail messages; receiving a status code from the first forest using the e-mail message protocol, the status code indicating whether or not the first forest is a forest that stores the particular candidate message inbox corresponding to where the particular recipient receives e-mail messages; and based upon the status code, determining if the e-mail message should be forwarded to the first forest using the e-mail message protocol for subsequent delivery to the particular candidate message inbox corresponding to where the particular recipient receives e-mail messages, or if further recipient inquiries should be sent using the e-mail messaging protocol to other forests from among the plurality of forests, the other forests storing other different subsets of the plurality of message inboxes for corresponding other subsets of the plurality of message recipients, the further recipient inquiries inquiring whether or not the other forests are forests that store the particular other candidate message boxes corresponding to where the particular recipient receives e-mail messages; wherein based on the status code it is determined that the e-mail message should be forwarded to the first forest is a forest that stores the particular for delivery to the candidate message inbox which corresponds to where the particular recipient receives messages, the method further comprising an act of: storing information identifying the first forest as a forest that stores the particular message inbox corresponding to where the particular recipient receives e-mail messages; further comprising acts of sending a second further recipient inquiry using the e-mail messaging protocol to a second forest from among the plurality of forests, the second forest storing a second subset of the plurality of message inboxes for corresponding second subsets of the plurality of message recipients, the second further recipient inquiry sending at least the user name portion of the destination address and inquiring whether or not the second forest is also a forest that stores an other particular a second candidate message inbox corresponding to where the particular recipient having the user name receives e-mail messages; receiving an additional status code from the second forest using the e-mail message protocol that indicates whether or not the second forest is a forest that stores the other particular second candidate message inbox corresponding to where the particular recipient receives e-mail messages; and based on upon the additional status code, determining if the message should be forwarded to the second forest for subsequent delivery to the other particular second candidate message inbox corresponding to where the specified recipient receives e-mail messages; wherein based on the additional status code it is determined that the e-mail message should also be forwarded to the second forest for delivery to the second candidate message inbox corresponding to where the particular recipient also receives e-mail messages, the method further comprising an act of: storing additional information identifying the second forest as a forest that also stores the particular message inbox corresponding to where the particular recipient receives e-mail messages.