Exhibit 99.4 EXECUTION COPY VOTING AGREEMENT dated as of October 2, 2000 (this "Agreement"), among JERE W. THOMPSON, JR. ("JWT") and the parties ---------- --- listed on Schedule A attached hereto (each, a "Shareholder" and, ----------- collectively, the "Shareholders"). ------------ WHEREAS McLeodUSA Incorporated, a Delaware corporation ("Parent"), ------ Cactus Acquisition Corp., a Delaware corporation and a wholly owned subsidiary of Parent ("Sub"), and CapRock Communications Corp., a Texas corporation (the --- "Company"), propose to enter into an Agreement and Plan of Merger dated as of - -------- the date hereof (as the same may be amended or supplemented, the "Merger ------ Agreement"; terms used but not defined herein shall have the meanings set forth - --------- in the Merger Agreement) providing for, among other things, the merger of Sub with and into the Company upon the terms and subject to the conditions set forth in the Merger Agreement; WHEREAS each Shareholder owns (of record or beneficially) the number of shares of Company Common Stock set forth opposite such Shareholder's name on Schedule A hereto (such shares, together with any other shares of capital stock of the Company or other voting securities of the Company acquired (of record or beneficially) by the Shareholders after the date hereof and during the term of this Agreement (including through the exercise of any warrants, stock options or similar instruments), being collectively referred to herein as the "Subject ------- Shares"); and - ------ WHEREAS as a condition to its willingness to enter into the Merger Agreement, Parent has required that each Shareholder enter into this Agreement. NOW, THEREFORE, in consideration of the foregoing and the representations, warranties, covenants and agreements set forth herein and in the Merger Agreement, the parties hereto agree as follows: 1 SECTION 1. Representations and Warranties of Each Shareholder. Each --------------------------------------------------- Shareholder hereby represents and warrants to JWT as follows: (a) Organization; Authority; Execution and Delivery; -------------------------------------------------- Enforceability. Such Shareholder (i) is duly organized, validly existing and in - --------------- good standing under the laws of its jurisdiction of organization, if applicable, and (ii) has the requisite corporate, company, partnership or other power and authority to execute and deliver this Agreement, to consummate the transactions contemplated hereby and to comply with the terms hereof. The execution and delivery by such Shareholder, the consummation by such Shareholder of the transactions contemplated hereby and compliance by such Shareholder with the provisions hereof have been duly authorized by all necessary corporate, company, partnership or other action on the part of such Shareholder and no other corporate, company, partnership or other proceedings on the part of such Shareholder are necessary to authorize this Agreement, to consummate the transactions contemplated hereby or to comply with the provisions hereof. This Agreement has been duly executed and delivered by such Shareholder and constitutes a valid and binding obligation of such Shareholder and, assuming this Agreement constitutes a valid and binding obligation of Parent, is enforceable against such Shareholder in accordance with its terms, except as enforceability may be limited by bankruptcy, insolvency, fraudulent conveyance, reorganization, moratorium and other laws affecting the rights and remedies of creditors generally and general principles of equity (whether considered in a proceeding in equity or at law). The execution and delivery of this Agreement, the consummation of the transactions contemplated hereby and compliance with the provisions hereof do not and will not conflict with, or result in any violation or breach of, or default (with or without notice or lapse of time, or both) under, or give rise to a right of, or result in, termination, cancelation or acceleration of any obligation or to loss of a material benefit under, or result in the creation of any Lien in or upon any of the properties or assets of such Shareholder under, or give rise to any increased, additional, accelerated or guaranteed rights or entitlements under, any provision of (i) any certificate of incorporation or by-laws, partnership agreement or limited liability company 2 agreement (or similar organizational documents) of such Shareholder, (ii) any Contract to which such Shareholder is a party or any of the properties or assets of such Shareholder is subject or (iii) subject to the governmental filings and other matters referred to in the following sentence, any (A) statute, law, ordinance, rule or regulation or (B) judgment, order or decree, in each case, applicable to such Shareholder or its properties or assets, other than, in the case of clauses (ii) and (iii), any such conflicts, violations, breaches, defaults, rights, losses, Liens or entitlements that individually or in the aggregate could not reasonably be expected to impair in any material respect the ability of any Shareholder to perform its obligations under this Agreement or prevent or materially impede or delay the consummation of any of the transactions contemplated by this Agreement. No consent, approval, order or authorization of, or registration, declaration or filing with, any Governmental Entity is required by or with respect to such Shareholder in connection with the execution and delivery of this Agreement by such Shareholder, the consummation by such Shareholder of the transactions contemplated hereby or the compliance by such Shareholder with the provisions hereof, except for (1) filings under the HSR Act and any other applicable competition, merger control, antitrust or similar law or regulation, (2) filings with the SEC of such reports under the Exchange Act as may be required in connection with this Agreement and the transactions contemplated hereby and (3) such other consents, approvals, orders, authorizations, registrations, declarations and filings the failure of which to be obtained or made individually or in the aggregate could not reasonably be expected to impair in any material respect the ability of such Shareholder to perform its obligations under this Agreement or prevent or materially impede or delay the consummation of any of the transactions contemplated hereby. (b) The Subject Shares. Such Shareholder is the record and ------------------- beneficial owner of, and has good and marketable title to, the Subject Shares set forth opposite its name on Schedule A hereto, free and clear of any Liens except as set forth on Schedule A. As of the date hereof, other than as set forth on Schedule A hereto, such Shareholder does not own (of record or beneficially) any 3 shares of capital stock of the Company, and no Shareholder owns (of record or beneficially) any options, warrants, rights or other similar instruments to acquire any capital stock or other voting securities of the Company. Except as set forth on Schedule A, such Shareholder has the sole right to Transfer (as defined in Section 3(c)) and direct the voting of the Subject Shares set forth opposite its name on Schedule A hereto, and none of such Subject Shares is subject to any voting trust or other agreement, arrangement or restriction with respect to the Transfer or the voting of such Subject Shares, except as set forth in Sections 3 and 4 of this Agreement. SECTION 2. [Intentionally Omitted] SECTION 3. Covenants of Each Shareholder. Each Shareholder covenants ------------------------------ and agrees as follows: (a) At any meeting of the shareholders of the Company called to vote upon the Merger Agreement, the Merger or any of the other transactions contemplated by the Merger Agreement, or at any adjournment or postponement thereof, or in any other circumstances upon which a vote, consent, adoption or other approval (including by written consent solicitation) with respect to the Merger Agreement, the Merger or any of the other transactions contemplated by the Merger Agreement is sought, such Shareholder shall vote (or cause to be voted) all the Subject Shares of such Shareholder (owned of record or beneficially) in favor of, and shall consent in writing to (or cause to be consented in writing to), the approval of the Merger Agreement and the terms thereof and of the Merger and each of the other transactions contemplated by the Merger Agreement. (b) At any meeting of the shareholders of the Company, or at any adjournment or postponement thereof, or in any other circumstances upon which a vote, consent, adoption or other approval (including by written consent solicitation) is sought, such Shareholder shall vote (or cause to be voted) all the Subject Shares of such Shareholder (owned of record or beneficially) against, and shall not consent in writing to (and shall cause not to be consented in writing to), any of the following (or any agreement to enter into, effect, facilitate or support any 4 of the following): (i) any Company Takeover Proposal or transaction or occurrence that if proposed and offered to the Company or its shareholders (or any of them) would constitute a Company Takeover Proposal (collectively, "Alternative Transactions") or (ii) any amendment of the Company's Articles of ------------------------ Incorporation or By-laws or other proposal, action or transaction involving the Company or any of its Subsidiaries or any of its shareholders, which amendment or other proposal, action or transaction could reasonably be expected to prevent or materially impede or delay the consummation of the Merger or the other transactions contemplated by the Merger Agreement or the consummation of the transactions contemplated by this Agreement or to deprive Parent of any material portion of the benefits anticipated by Parent to be received from the consummation of the Merger or the other transactions contemplated by the Merger Agreement or this Agreement, or change in any manner the voting rights of the Company Common Stock (collectively, "Frustrating Transactions"). ------------------------ (c) Other than pursuant to this Agreement, such Shareholder shall not (i) sell, transfer, pledge, assign or otherwise dispose of (including by gift) (collectively, "Transfer"), or consent to or permit any Transfer of, any -------- Subject Shares of such Shareholder or any interest therein, or enter into any Contract, option or other arrangement (including any profit sharing arrangement) with respect to the Transfer of, or the creation or offer of any derivative security in respect of, any Subject Shares of such Shareholder, to or with any person or (ii) enter into any voting arrangement, whether by proxy, voting agreement or otherwise, with respect to any Subject Shares of such Shareholder, and shall not commit or agree to take any of the foregoing actions. Such Shareholder shall not, nor shall such Shareholder permit any entity under such Shareholder's control to, deposit any Subject Shares of such Shareholder in a voting trust. (d) Such Shareholder shall not, nor shall such Shareholder permit any of its Subsidiaries to, nor shall it authorize or permit any director, officer, employee or partner of such Shareholder or any of its Subsidiaries or any Representative of such Shareholder or any of its Subsidiaries to, directly or indirectly, (i) solicit, 5 initiate or encourage, or take any other action designed to facilitate, any Alternative Transaction or Frustrating Transaction, (ii) enter into any agreement with respect to any Alternative Transaction or Frustrating Transaction or (iii) except to the extent the Company shall have previously done so in accordance with Section 4.02(a) of the Merger Agreement, enter into, continue or otherwise participate in any discussions or negotiations regarding, or furnish to any person any information with respect to, or otherwise cooperate in any way with, or assist or participate in any effort or attempt by any person with respect to, any Alternative Transaction or Frustrating Transaction. (e) Such Shareholder shall use its commercially reasonable efforts to take, or cause to be taken, all actions and to do, or cause to be done, and to assist and cooperate with the other parties in doing all things necessary, proper or advisable to consummate and make effective, in the most expeditious manner practicable, the transactions contemplated by this Agreement and the Merger Agreement. Such Shareholder shall not commit or agree to take any action inconsistent with the transactions contemplated by this Agreement or the transactions contemplated by the Merger Agreement. (f) Such Shareholder shall not, nor shall such Shareholder permit any of its Subsidiaries to, nor shall it authorize or permit any director, officer, employee or partner of such Shareholder or any of its Subsidiaries or any Representative of such Shareholder or any of its Subsidiaries to, directly or indirectly, issue any press release or make any other public statement with respect to the Merger Agreement, this Agreement, the voting and option agreement dated the date hereof among Parent and certain shareholders of the Company and the voting agreement dated the date hereof among Parent and certain Shareholders of the Company (collectively, the "Voting and Option Agreement"), the Merger or any of the other transactions contemplated by the Merger Agreement, the Voting and Option Agreement or this Agreement, except as may be required by applicable law. 6 (g) Notwithstanding anything to the contrary contained herein, nothing in this Section 3 shall prohibit any Shareholder from, in his capacity as an officer and/or director of the Company, taking any actions, on behalf of the Company, that the Company is permitted to take under Section 4.02 of the Merger Agreement. SECTION 4. Grant of Proxy; Appointment of Proxy. (a) Each ------------------------------------- Shareholder hereby irrevocably grants to, and appoints JWT, such Shareholder's proxy and attorney-in-fact (with full power of substitution), for and in the name, place and stead of such Shareholder, to vote all such Shareholder's Subject Shares (owned of record or beneficially), or grant a consent or approval in respect of such Subject Shares, (i) in favor of the approval of the Merger Agreement and the terms thereof and of the Merger and each of the other transactions contemplated by the Merger Agreement and (ii) against any Alternative Transaction or any Frustrating Transaction. (b) Each Shareholder represents that any proxies heretofore given in respect of such Shareholder's Subject Shares are not irrevocable, and that all such proxies are hereby revoked. (c) Each Shareholder hereby affirms that the irrevocable proxy set forth in this Section 4 is given in connection with the execution of the Merger Agreement and that such irrevocable proxy is given to secure the performance of the duties of such Shareholder under this Agreement. Each Shareholder hereby further affirms that the irrevocable proxy is coupled with an interest and may under no circumstances be revoked unless and until this Agreement is terminated in accordance with Section 8 of this Agreement. Each Shareholder hereby ratifies and confirms all that such irrevocable proxy may lawfully do or cause to be done by virtue hereof. Each such irrevocable proxy is executed and intended to be irrevocable in accordance with the provisions of Article 2.29 of the TBCA. SECTION 5. Further Assurances. Each Shareholder shall from time to ------------------- time execute and deliver, or cause to be executed and delivered, such additional or further consents, documents and other instruments as Parent may 7 request for the purpose of effectuating the matters covered by this Agreement, including the grant of proxies set forth in Section 4. SECTION 6. Certain Events. (a) Each Shareholder agrees that this --------------- Agreement and the obligations hereunder shall attach to such Shareholder's Subject Shares and shall be binding upon any person or entity to which legal or beneficial ownership of such Subject Shares shall pass, whether by operation of law or otherwise, including such Shareholder's heirs, guardians, administrators or successors, and such Shareholder further agrees to take all actions necessary to effectuate the foregoing. Each Shareholder agrees that each certificate representing the Subject Shares of such Shareholder shall be inscribed with the legend required by Section 6(b). In the event of any stock split, stock dividend, reclassification, merger, reorganization, recapitalization or other change in the capital structure of the Company affecting the capital stock of the Company, the number of Subject Shares listed on Schedule A hereto opposite the name of each Shareholder shall be adjusted appropriately. In addition, in the event of any other acquisition of additional shares of capital stock of the Company or other voting securities of the Company by any Shareholder (including through the exercise of any warrants, stock options or similar instruments), the number of Subject Shares listed on Schedule A hereto opposite the name of such Shareholder shall be adjusted appropriately. This Agreement and the representations, warranties, covenants, agreements and obligations hereunder shall attach to any additional shares of capital stock of the Company or other voting securities of the Company issued to or acquired by any Shareholder directly or indirectly (including through the exercise of any warrants, stock options or similar instruments). (b) Each Shareholder shall cause the certificated Subject Shares held by him to have a legend placed conspicuously on such certificate to the following effect: The shares of common stock evidenced by this certificate are subject to a Voting Agreement dated October 2, 2000 entered into by the record owner of such shares and Jere W. Thompson, Jr. 8 For all uncertificated Subject Shares each Shareholder shall request that the Company send notice of such voting agreement as required by Article 2.19(D) of the TBCA. Each Shareholder shall cause a counterpart of this Agreement to be deposited with the Company at its principal place of business or registered office where it shall be subject to the same right of examination by a shareholder of the Company, in person or by agent or attorney, as are the books and records of the Company. SECTION 7. Assignment. Neither this Agreement nor any of the rights, ----------- interests or obligations under this Agreement shall be assigned, in whole or in part, by operation of law or otherwise, by any of the parties hereto without the prior written consent of Parent. Any purported assignment in violation of this Section 7 shall be void. Subject to the preceding sentences of this Section 7, this Agreement shall be binding upon, inure to the benefit of and be enforceable by, the parties hereto and their respective successors and assigns. SECTION 8. Termination. Except as set forth below, this Agreement ------------ shall terminate upon the earliest of (i) the Effective Time and (ii) the termination of the Merger Agreement in accordance with its terms. In the event of the termination of this Agreement pursuant to this Section 8, except as set forth herein, this Agreement shall forthwith become null and void, there shall be no liability on the part of any of the parties, and except as set forth in this Section 8 all rights and obligations of each party hereto shall cease; provided, however, that no such termination of this Agreement shall relieve any - -------- ------- party hereto from any liability for any willful and material breach of any provision of this Agreement prior to termination. SECTION 9. General Provisions. (a) Amendments. This Agreement may ------------------- ----------- not be amended except by an instrument in writing signed by all of the parties hereto. 9 (b) Notices. All notices, requests, claims, demands and other -------- communications under this Agreement shall be in writing and shall be deemed given if delivered personally, telecopied (with confirmation) or sent by overnight or same-day courier (providing proof of delivery) to JWT and to the Shareholders at their respective addresses set forth on Schedule A hereto (or at such other address for a party as shall be specified by like notice). (c) Interpretation. When a reference is made in this Agreement to a --------------- Section or a Schedule, such reference shall be to a Section of, or a Schedule to, this Agreement unless otherwise indicated. The headings contained in this Agreement are for reference purposes only and shall not affect in any way the meaning or interpretation of this Agreement. Whenever the words "include", "includes" or "including" are used in this Agreement, they shall be deemed to be followed by the words "without limitation". The words "hereof", "herein" and "hereunder" and words of similar import when used in this Agreement shall refer to this Agreement as a whole and not to any particular provision of this Agreement. The term "or" is not exclusive. The definitions contained in this Agreement are applicable to the singular as well as the plural forms of such terms. Any agreement or instrument defined or referred to herein or in any agreement or instrument that is referred to herein means such agreement or instrument as from time to time amended, modified or supplemented. References to a person are also to its permitted successors and assigns. (d) Counterparts; Effectiveness. This Agreement may be executed in ---------------------------- one or more counterparts, all of which shall be considered one and the same agreement and shall become effective when one or more counterparts have been signed by each of the parties hereto and delivered to the other party. The effectiveness of this Agreement shall be conditioned upon the execution and delivery of the Merger Agreement by each of the parties thereto. (e) Entire Agreement; No Third-Party Beneficiaries. This Agreement ----------------------------------------------- (including the documents and instruments referred to herein) (i) constitutes the entire agreement and supersedes all prior agreements and 10 understandings, both written and oral, among the parties hereto with respect to the subject matter of this Agreement and (ii) is not intended to confer upon any person other than the parties hereto (and the persons specified as proxies in Section 4) any rights or remedies. (f) Governing Law. This agreement shall be governed by and construed -------------- in accordance with the laws of the State of Delaware, without regard to its principles of conflicts of laws (except to the extent that the provisions of the TBCA shall be mandatorily applicable to this Agreement). (g) Severability. If any term or other provision of this Agreement ------------- is invalid, illegal or incapable of being enforced by any rule of law or public policy, all other conditions and provisions of this Agreement shall nevertheless remain in full force and effect. Upon such determination that any term or other provision is invalid, illegal or incapable of being enforced, the parties hereto shall negotiate in good faith to modify this Agreement so as to effect the original intent of the parties as closely as possible to the fullest extent permitted by applicable law in an acceptable manner and to the end that the transactions contemplated hereby are fulfilled to the extent possible. SECTION 10. Enforcement. The parties agree that irreparable damage ------------ would occur and that the parties will not have any adequate remedy at law in the event that any of the provisions of this Agreement were not performed in accordance with their specific terms or were otherwise breached. It is accordingly agreed that the parties shall be entitled to an injunction or injunctions to prevent breaches of this Agreement and to enforce specifically the terms and provisions of this Agreement in any court of the United States located in the State of Delaware or in any Delaware state court, this being in addition to any other remedy to which they are entitled at law or in equity. In addition, each of the parties hereto (i) consents to submit itself to the personal jurisdiction of any court of the United States located in the State of Delaware or of any Delaware state court in the event any dispute arises out of this Agreement or the transactions contemplated by this 11 Agreement, (ii) agrees that it will not attempt to deny or defeat such personal jurisdiction by motion or other request for leave from any such court, (iii) agrees that it will not bring any action relating to this Agreement or the transactions contemplated by this Agreement in any court other than a court of the United States located in the State of Delaware or a Delaware state court and (iv) waives any right to trial by jury with respect to any claim or proceeding related to or arising out of this Agreement or any transaction contemplated by this Agreement. SECTION 11. Agent for Service of Process. Each Shareholder hereby ----------------------------- appoints the Company, with offices on the date hereof as provided for in Section 8.02 of the Merger Agreement, as its authorized agent (the "Authorized Agent"), ---------------- upon whom process may be served in any suit, action or proceeding arising out of or relating to this Agreement or any transaction contemplated by this Agreement that may be instituted in any court described in Section 10. Each Shareholder agrees to take any and all action, including the filing of any and all documents, that may be necessary to establish and continue such appointment in full force and effect as aforesaid. Each Shareholder agrees that service of process upon the Authorized Agent shall be, in every respect, effective service of process upon such Shareholder. SECTION 12. Shareholder Capacity. No person executing this Agreement --------------------- who is or becomes during the term hereof a director or officer of the Company makes any agreement or understanding herein in his or her capacity as such director or officer. Each Shareholder signs solely in his or her capacity as the record holder and beneficial owner of, or the trustee of a trust whose beneficiaries are the beneficial owners of, such Shareholder's Subject Shares and nothing herein shall limit or affect any actions taken by a Shareholder in its capacity as an officer or director of the Company to the extent specifically permitted by the Merger Agreement. 12 IN WITNESS WHEREOF, JWT has signed this Agreement and each Shareholder has caused this Agreement to be signed by its officer thereunto duly authorized, all as of the date first written above. /s/ Jere W. Thompson, Jr. -------------------------------- Jere W. Thompson, Jr. 13 SHAREHOLDERS: /s/ Ignatius W. Leonards __________________________ Ignatius W. Leonards SHAREHOLDERS: /s/ John P. Thompson ________________________ John P. Thompson THE HAYDEN COMPANY, by /s/ John P. Thompson ________________________ Name: John P. Thompson Title: President SHAREHOLDERS: /s/ Joe C. Thompson, Jr. ---------------------------- Joe C. Thompson THE FLORIDA COMPANY, by /s/ Joe C. Thompson, Jr. ---------------------------- Name: Joe C. Thompson, Jr. Title: President SHAREHOLDERS: /s/ Patrick J. Thompson ________________________ Patrick J. Thompson SHAREHOLDERS: /s/ David E. Thompson ________________________ David E. Thompson