FORM OF VOTING AGREEMENT

Exhibit 10.1

FORM OF VOTING AGREEMENT

This Voting Agreement (this “Agreement”) is entered into as of September 17, 2007, by and among PAETEC Holding Corp., a Delaware corporation (“Buyer”), McLeodUSA Incorporated, a Delaware corporation (“Seller”), and the stockholder of Buyer identified on the signature pages hereto (the “Buyer Stockholder”).

WHEREAS, as of the date of this Agreement, Buyer, Seller and PS Acquisition Corp., a Delaware corporation and a wholly-owned subsidiary of Buyer (“Merger Sub”), are entering into an Agreement and Plan of Merger (the “Merger Agreement”) pursuant to which, and subject to the terms and conditions of which, Merger Sub will merge with and into Seller and each share of common stock, par value $0.01 per share, of Seller will be converted into the right to receive 1.30 shares of common stock, par value $0.01 per share, of Buyer (the “Buyer Common Stock”) (such transaction, the “Merger”). Capitalized terms used herein without being defined have the same meanings given to such terms in the Merger Agreement;

WHEREAS, the Buyer Stockholder beneficially owns, and has sole voting power or (together with one or more affiliates controlled by the Buyer Stockholder) shared voting power with respect to, the outstanding shares of Buyer Common Stock identified as being held by the Buyer Stockholder on Exhibit A hereto (such shares of Buyer Common Stock, together with any voting securities of Buyer issued or exchanged with respect to such shares of Buyer Common Stock upon any recapitalization, reclassification, merger, consolidation, spin-off, partial or complete liquidation, stock dividend, split-up or combination of the securities of Buyer or any other change in Buyer’s capital structure, the “Covered Outstanding Shares”);

WHEREAS, the Buyer Stockholder owns of record the options to purchase shares of Buyer Common Stock (the “Buyer Options”) and the stock units representing Buyer Common Stock (the “Buyer Stock Units”) identified as being held by the Buyer Stockholder on Exhibit A hereto (the shares of Buyer Common Stock subject to such Buyer Options and Buyer Stock Units, together with any voting securities of Buyer issued or exchanged with respect to such shares of Buyer Common Stock upon any recapitalization, reclassification, merger, consolidation, spin-off, partial or complete liquidation, stock dividend, split-up or combination of the securities of Buyer or any other change in Buyer’s capital structure, together with the Covered Outstanding Shares, the “Covered Shares”); and

WHEREAS, in connection with the execution of the Merger Agreement, the Seller has requested that the Buyer Stockholder and certain other holders of Buyer Common Stock execute and deliver this Agreement;

NOW, THEREFORE, in consideration of the premises, the mutual covenants and agreements contained herein and other good and valuable consideration, the receipt of which are hereby acknowledged, the Buying Stockholder, Buyer and Seller hereby agree as follows:

1. Cooperation by Buyer Stockholder. Unless and until this Agreement shall be terminated pursuant to paragraph 4, the Buyer Stockholder agrees that, solely in such Buyer Stockholder’s capacity as a stockholder of Buyer: (a) at the Buyer Stockholders Meeting to be held pursuant to Section 5.1(c) of the Merger Agreement, the Buyer Stockholder shall cause all Covered Shares which are outstanding and beneficially owned by Buyer Stockholder on the record date of the Buyer Stockholders Meeting (the “Eligible Shares”) to be counted as present thereat for the purpose of establishing a quorum and voted in person or by proxy in favor of the issuance of shares of Buyer Common Stock in the Merger pursuant to the Merger Agreement; (b) the Buyer Stockholder shall not take or permit the Buyer Stockholder’s representatives to take actions inconsistent with his or their obligations under this Agreement; and (c) the Buyer Stockholder agrees that, if requested by Seller, the Buyer Stockholder shall appoint and authorize one or more persons designated by Seller as the agent, proxy and attorney-in-fact for the Buyer Stockholder, with full power of substitution and resubstitution, solely to cause the Eligible Shares to be counted as present and to vote the Eligible Shares prior to the termination of this Agreement in accordance with clause (a) above. With respect to the agreement to grant proxy and power of attorney granted by the Buyer Stockholder under clause (c) above: (i) the Buyer Stockholder shall take such further action or execute such other instruments, at Buyer’s sole cost and expense, as may be reasonably necessary to effectuate the intent of such proxy; (ii) such proxy and power of attorney shall be irrevocable during the term of this Agreement, shall be deemed to be coupled with an interest sufficient in law to support an irrevocable proxy and shall revoke any and all prior proxies granted by the Buyer Stockholder inconsistent with such proxy; (iii) such power of attorney is a durable power of attorney; and (iv) such proxy and power of attorney shall terminate upon the termination of this Agreement.

2. Agreement to Retain. Unless and until this Agreement shall be terminated pursuant to paragraph 4, unless authorized in advance by Buyer’s Board of Directors and by Seller’s Board of Directors, the Buyer Stockholder, solely in the Buyer Stockholder’s capacity as a stockholder of Buyer, agrees (a) not to sell or otherwise transfer any of the Covered Shares or any economic, voting or other direct or indirect interest therein, and (b) not to grant a proxy or enter into any voting agreement concerning any of the Covered Shares (except, in each case, for the voting agreement and agreement to appoint proxy under paragraph 1 and the fulfillment of all other agreements and obligations of the Buyer Stockholder hereunder); provided that, notwithstanding the foregoing, the Buyer Stockholder shall be permitted to sell or otherwise transfer up to 33% [or 3,000,000 in the case of Arunas A. Chesonis] of the Covered Shares in the aggregate during such period.

3. Representations and Warranties. The Buyer Stockholder hereby represents and warrants to Buyer and Seller that: (a) the Buyer Stockholder has the power and authority to enter into and deliver this Agreement and perform its obligations under this Agreement; (b) this Agreement is binding on the Buyer Stockholder and enforceable in accordance with its terms, except as enforceability may be limited by Creditors’ Laws; (c) the execution and delivery of this Agreement and the performance by the Buyer

2

Stockholder of his obligations hereunder do not require the authorization, consent, approval, license, exemption or other action by any third party or governmental authority, do not violate applicable law or conflict with or result in a breach of any of the Buyer Stockholder’s contractual obligations; (d) the Buyer Stockholder beneficially owns and has sole voting power or (together with one or more affiliates controlled by the Buyer Stockholder) shared voting power with respect to the Covered Outstanding Shares identified as being held by the Buyer Stockholder on Exhibit A to this Agreement, and such shares are free and clear of any liens, claims or encumbrances of any kind other than those arising from the Buyer Stockholder’s obligations under this Agreement; and (e) other than the Covered Outstanding Shares that are identified as to the Buyer Stockholder on Exhibit A to this Agreement, the Buyer Stockholder does not own, of record or beneficially, any outstanding voting securities of Buyer, other than voting securities for which the Buyer Stockholder does not have shared voting power together with one or more affiliates controlled by the Buyer Stockholder.

4. Termination of Agreement. This Agreement shall remain in full force and effect until, and the provisions of paragraphs 1 through 3 (inclusive) shall terminate upon, the earliest to occur of any of the following: (a) the Merger Agreement, as it may be amended or modified from time to time, is terminated in accordance with its terms; (b) the Merger is consummated; (c) the parties hereto execute a written agreement to terminate this Agreement; and (d) the Outside Date (as defined in the Merger Agreement in effect on the date hereof).

5. Notice. All notices, requests, claims, demands and other communications (“Notices”) under this Agreement shall be in writing and sent by certified or registered mail, return receipt requested, a recognized overnight courier service, telecopier or personal delivery, as follows: (a) if to Buyer or to the Buyer Stockholder, to: PAETEC Holding Corp., One PAETEC Plaza, 600 Willowbrook Office Park, Fairport, New York 14450, Attention: General Counsel, Telecopier: (585)  ###-###-####, with a required copy to: Hogan & Hartson L.L.P., 8300 Greensboro Drive, McLean, Virginia 22102, Attention: Richard J. Parrino and Thomas E. Repke, Telecopier: (703)  ###-###-#### and (b) if to Seller, to: McLeodUSA Incorporated, 16479 Dallas Pkwy, Suite 700, Bent Tree Towers II, Dallas, Texas 75248, Attention: Bernie Zuroff, Telecopier: (469)  ###-###-####, with a required copy to: Ropes & Gray LLP, One International Place, Boston, Massachusetts 02110, Attention: Robert L. Nutt and Keith F. Higgins, Telecopier: (617)  ###-###-####. All Notices shall be deemed to have been duly given: when delivered by hand, if personally delivered; when delivered by courier, if delivered by commercial overnight courier service; five business days after being deposited in the mail, postage prepaid, if mailed; and when receipt is acknowledged, if telecopied. A party may change its address for purposes of this Agreement by Notice in accordance with this paragraph 5.

6. Entire Agreement. This Agreement supersedes all prior agreements between the parties with respect to its subject matter and constitutes a complete and exclusive statement of the terms of the agreement between the parties with respect to its subject matter.

3

7. No Other Rights. Nothing in this Agreement shall be considered to give any person other than the parties any legal or equitable right, claim or remedy under or in respect of this Agreement or any provision of this Agreement. This Agreement and all of its provisions are for the sole and exclusive benefit of the parties and their respective successors and permitted assigns.

8. Equitable Relief. Each of the parties hereto acknowledges that a breach by it of any provision contained in this Agreement will cause the other parties to sustain damage for which they would not have an adequate remedy at law for money damages, and therefore each of the parties hereto agrees that in the event of any such breach, the aggrieved party shall be entitled to the remedy of specific performance of such agreement and injunctive and other equitable relief in addition to any other remedy to which it may be entitled, at law or in equity.

9. Severability. If any provision of this Agreement is held invalid or unenforceable by a court of competent jurisdiction, the other provisions of this Agreement shall remain in full force and effect. Any provision of this Agreement which is held invalid or unenforceable only in part shall remain in full force and effect to the extent not held invalid or unenforceable.

10. Headings. All references in this Agreement to “paragraph” or “paragraphs” refer to the corresponding numbered paragraph or paragraphs of this Agreement. All words used in this Agreement shall be construed to be of the appropriate gender or number as the context requires. Unless otherwise expressly provided, the word “including” does not limit the preceding words or terms.

11. Counterparts. This Agreement may be executed in one or more counterparts, each of which shall be considered an original copy of this Agreement and all of which, when taken together, shall be considered to constitute one and the same agreement.

12. Governing Law. This Agreement shall be governed by and construed in accordance with the laws of the State of Delaware without regard to that state’s conflicts of laws principles.

13. Amendments; Waivers. Any amendment or modification of or to any provision of this Agreement, and any consent to any departure of any party from the terms of any provision of this Agreement, shall be effective only if it is made or given in writing and signed by each party. Notwithstanding the foregoing sentence, any failure of any of the parties to comply with any obligation, covenant, agreement or condition herein may be waived by any party entitled to the benefits thereof only by a written instrument signed by such party granting such waiver, but such waiver or failure to insist upon strict compliance with such obligation, covenant, agreement or condition shall not operate as a waiver of, or estoppel with respect to, any subsequent or other failure. The failure of any party to assert any of its rights under this Agreement or otherwise shall not constitute a waiver of those rights.

4

14. Successors and Assigns. This Agreement shall apply to, be binding in all respects upon and inure to the benefit of the parties and their respective successors and permitted assigns. No party may assign any of its rights under this Agreement without the prior written consent of each of the other parties.

5

IN WITNESS WHEREOF, the parties have caused this Agreement to be duly executed as of the date first above written.