<PAGE>
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
<PAGE>
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
<PAGE>
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
<PAGE>
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
<PAGE>
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
<PAGE>
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
<PAGE>
(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
<PAGE>
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
<PAGE>
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
<PAGE>
(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
<PAGE>
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
<PAGE>
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
<PAGE>
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
<PAGE>
SHAREHOLDERS:
/s/ Ignatius W. Leonards
__________________________
Ignatius W. Leonards
<PAGE>
SHAREHOLDERS:
/s/ John P. Thompson
________________________
John P. Thompson
THE HAYDEN COMPANY,
by /s/ John P. Thompson
________________________
Name: John P. Thompson
Title: President
<PAGE>
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
<PAGE>
SHAREHOLDERS:
/s/ Patrick J. Thompson
________________________
Patrick J. Thompson
<PAGE>
SHAREHOLDERS:
/s/ David E. Thompson
________________________
David E. Thompson
