Exhibit 99.1

For Immediate Release:
October 29, 2004

Metrocall Contact:
Brett Mankey
(703) 660-6677x6231

Metrocall Holdings, Inc. Announces Receipt of Notices from Stockholders
Purporting to Exercise Appraisal Rights

     Alexandria, VA, Thursday, October 29, 2004 — Metrocall Holdings, Inc. (NASDAQ: MTOH) today announced that Metrocall stockholders claiming to hold in the aggregate approximately 8.7% of the fully-diluted common stock of Metrocall have delivered to Metrocall written notice of their intent to exercise their right under Delaware law to seek appraisal of their shares of Metrocall common stock in connection with the proposed merger of Metrocall and Arch Wireless, Inc. The exercise by holders of more than 8% of the fully-diluted common stock of Metrocall of their appraisal rights, if valid and not withdrawn, would constitute a failure of one of the conditions to the merger. Under the merger agreement, Metrocall and Arch may jointly waive this condition with the approval of their respective boards of directors. Neither the Metrocall nor the Arch board has made any determination at this time as to whether or not to waive this condition. The financing commitment for the cash election portion of the merger consideration payable to Metrocall stockholders is also conditioned on the 8% threshold not being met and would require a waiver for the financing to be available. Subject to discussion with its board and the Arch board on this issue, Metrocall intends to proceed with the special stockholder meeting scheduled for November 8, 2004 to consider the merger.

If Metrocall and Arch waive this condition and the merger is completed, any Metrocall stockholder who validly exercises appraisal rights will not be entitled to participate in the $150 million cash election to be paid to Metrocall stockholders in the merger with respect to the shares for which they validly exercised their right to seek appraisal, unless such exercise is withdrawn prior to 5:00 p.m. EST on November 5, 2004, the deadline for Metrocall stockholders to make cash elections. Instead, any such stockholder who exercises appraisal rights and complies with the requirements of Delaware law would receive the appraised value of their shares as determined by the Delaware Court of Chancery following a hearing on a petition filed by such stockholder. In the event that any such stockholder does not do so, such stockholder would receive the common stock of USA Mobility, the parent company of Metrocall and Arch following consummation of

the merger, as provided in the merger agreement, but would have waived its right to participate in the $150 million cash election.

About Metrocall Holdings

     Metrocall Holdings, Inc., headquartered in Alexandria, Virginia, is a leading provider of paging products and other wireless services to the business, government and healthcare communities. In addition to its reliable, nationwide one-way networks, Metrocall’s two-way network has the largest high-powered terrestrial ReFLEX footprint in the United States with roaming partners in Canada, Mexico and the Caribbean. Metrocall Wireless is the preferred ReFLEX wireless data network provider for many of the largest telecommunication companies in the United States that source network services and resell under their own brand names. In addition to traditional numeric, one-way text and two-way paging, Metrocall also offers wireless e-mail solutions, as well as mobile voice and data services through AT&T Wireless and Nextel. Also, Metrocall offers Integrated Resource Management Systems with wireless connectivity solutions for medical, business, government and other campus environments. Metrocall focuses on the business-to-business marketplace and supports organizations of all sizes. For more information on Metrocall please visit our Web site and online store at www.metrocall.com or call 800-800-2337.

Safe Harbor Statement Under the Private Securities Litigation Reform Act

This press release includes “forward-looking statements,” within the meaning of the federal securities laws, that involve uncertainties and risks. These include statements regarding events or developments that Metrocall Holdings expects or anticipates will occur in the future. A number of risks and uncertainties could cause actual results, events, and developments to differ from expectations. Please refer to Metrocall’s most recent annual report on Form 10-K, and any subsequently filed reports on Form 10-Q and Form 8-K, as well as its other filings with the Securities and Exchange Commission, for a complete discussion of these and other important factors that could cause actual results to differ materially from those projected by these forward-looking statements.