Exhibit 99.1

For Immediate Release:
Monday, May 17, 2004

Metrocall Contact:
Timothy J. Dietz
Director, Corporate Communications
& Investor Relations
(703) 660-6677x6231
dietzt@metrocall.com

Metrocall Redeems Remaining Preferred Shares

All Long-term Debt and Preferred Stock Obligations Retired

     Alexandria, VA, Monday, May 17, 2004 — Metrocall Holdings, Inc. (NASDAQ:MTOH), a leading provider of paging and wireless messaging, today announced the voluntary redemption of the approximate 600,000 remaining shares of its 15% cumulative series A preferred stock (series A preferred). The per share redemption price is approximately $11.13 plus accrued dividends of $0.215. This redemption marks the early retirement of all of Metrocall’s debt and preferred stock obligations related to its 2002 Plan of Reorganization and was funded from $6.8 million of cash balances generated from operations.

     According to Metrocall President & CEO Vincent D. Kelly, “In little more than 19 months, Metrocall has retired all of the long-term debt and series A preferred stock obligations associated with our 2002 plan of reorganization, representing an important milestone for the Company, realized significantly ahead of schedule. This achievement is the result of the support, hard work and dedication of Metrocall’s customers and employees.”

     The repayment of approximately $81.5 million aggregate principal amount of Metrocall’s long-term debt securities was completed on June 30, 2003. Today’s $6.8 million redemption, together with three previous series A preferred redemption payments, brings the aggregate series A liquidation preference total to $66.8 million. In total, since its October 2002 reorganization, Metrocall has repaid and redeemed $148.3 million in obligations from cash balances generated from operations.

About Metrocall Wireless, Inc.

     Metrocall Wireless, 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. On March 29, 2004, Metrocall and Arch Wireless, Inc. announced a merger agreement that would result in a combination of the two businesses. That transaction is subject to several conditions, including shareholder and regulatory approvals. 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 of 1995

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.