Methods and systems are disclosed that allow for the exchange of voice mail messages between different VMSs of different service providers and/or in different networks by the transmission of such messages through a data network using a standard protocol of the data network. Methods and systems also are disclosed that validate message transactions among subscribers receiving regional messaging services over the PSTN. The subscribers are located in different geographic areas and may be provided their voice, facsimile or data messaging services by different companies. The present invention validates passing messages (data) among customers of potentially different companies located in different areas by assessing the validity of the transaction in light of a number of conditions, including applicable regulatory or business conditions.