Document:

<PAGE>

                                                                   Exhibit 10.19

                                                                [EXECUTION COPY]

                               VOTING AGREEMENT
                               ----------------

          THIS VOTING AGREEMENT (this "Agreement"), made as of this 4th day of
                                       ---------
February 2000, by and among PaeTec Corp., a Delaware corporation (the
"Corporation"); Alliance Cabletel Holdings, L.P., a Delaware limited partnership
 -----------
("Alliance"), Kline Hawkes California SBIC, L.P. ("Kline Hawkes"), The Union
  --------                                         ------------
Labor Life Insurance Company Separate Account P ("ULLICO"), and the individuals
                                                  ------
and/or entities listed on Schedule A hereto (together with Alliance, Kline
                          ----------
Hawkes and ULLICO, the "CCS Group Stockholders"); Arunas A. Chesonis ("Mr.
                        ----------------------                         ---
Chesonis"), Christopher Edgecomb, Trustee of the Christopher E. Edgecomb Living
--------
Trust dated April 25, 1998 ("Mr. Edgecomb"), and Jeffrey Sudikoff  ("Mr.
                             ------------                            ---
Sudikoff" and, together with Mr. Chesonis and Mr. Edgecomb, the "Principal
--------                                                         ---------
Stockholders"); Madison Dearborn Capital Partners III L.P., a Delaware limited
------------
partnership, Madison Dearborn Special Equity III, a Delaware limited
partnership, and Special Advisors Fund I LLC, a Delaware limited partnership
(collectively, "MDCP Group Stockholders"); Blackstone CCC Capital Partners,
                -----------------------
L.P., a Delaware limited partnership, Blackstone CCC Offshore Capital Partners,
L.P., a Cayman Islands limited partnership, and Blackstone Family Investment
Partnership III, L.P., a Delaware limited partnership (collectively the
"Blackstone Group Stockholders"); and Ares Leveraged Investment Fund L.P., a
------------------------------
Delaware limited partnership, Ares Leveraged Investment Fund L.P. II, a Delaware
limited partnership, Newcourt Commercial Finance Corporation, a Delaware
corporation, and UnionBanCal Equities, Inc., a California corporation
(collectively, the "Other Investor Stockholders").  The MDCP Group Stockholders,
                    ---------------------------
the Blackstone Group Stockholders and the Other Investor Stockholders are
hereinafter sometimes collectively referred to as the "Investor Stockholders"
                                                       ---------------------
and individually as an "Investor Stockholder." The Principal Stockholders, the
                        --------------------
CCS Group Stockholders and the Investor Stockholders are hereinafter sometimes
collectively referred to as the "Stockholders" and individually as a
                                 ------------
"Stockholder."
 -----------

                                   RECITALS
                                   --------

     WHEREAS, the Corporation is party to an Equity Purchase Agreement with the
Investor Stockholders, dated as of the date hereof (the "Purchase Agreement"),
                                                         ------------------
pursuant to which the Investor Stockholders will purchase shares of the
Corporation's Series A Convertible Preferred Stock, par value $0.01 per share
(the "Preferred Stock").
      ---------------

     WHEREAS, pursuant to Section 2 of the Purchase Agreement, it is a condition
precedent to the obligations of the parties thereunder to consummate the
transactions contemplated by the Purchase Agreement that the parties enter into
this Agreement.

     WHEREAS, pursuant to the terms of the Preferred Stock, as set forth in the
Corporation's Restated Certificate of Incorporation as of the date hereof, the
Investor Stockholders are entitled to nominate a certain number of persons for
election to the Corporation's board of directors (the "Board").
                                                       -----

     WHEREAS, pursuant to the Campuslink Stockholders Agreement (as defined
below), the CCS Group Stockholders are entitled to nominate a certain number of
persons for election to the Board.
<PAGE>

     WHEREAS, the Stockholders believe that it is in the best interests of the
parties hereto to formalize their agreements regarding certain voting matters
and to define certain rights, duties and obligations among the parties hereto.

     NOW, THEREFORE, the Stockholders and the Corporation agree as follows:

1.   Definitions.
     -----------

     1.1  "Affiliate" shall mean any Person that directly, or indirectly through
           ---------
one or more intermediaries, controls or is controlled by, or is under common
control with, any other Person, including, without limitation, any Affiliated
Fund.

     1.2  "Affiliated Fund" shall mean each corporation, trust, general or
           ---------------
limited partnership or other entity under common control with any Stockholder
which is managed by an Affiliate of Madison Dearborn Capital Partners III, L.P.
or Blackstone CCC Capital Partners, L.P.

     1.3  "Beneficially own" has the meaning set forth in Rule 13d-3 under the
           ----------------
Securities Exchange Act of 1934, as amended, as in effect on the date hereof.

     1.4  "Campuslink Stockholders Agreement" shall mean that certain
           ---------------------------------
Stockholders' Agreement, dated as of September 9, 1999, as amended as of the
date hereof, by and among the Corporation, the Principal Stockholders and the
other stockholders a party thereto.

     1.5  "Common Stock" shall mean, collectively, the Class A common stock, par
           ------------
value $0.01 per share, of the Corporation, and the Class B common stock, par
value $.01 per share, of the Corporation (the "Class B Common Stock").
                                               --------------------

     1.6  "Permitted Transferee" shall mean the transferee of any Securities of
           --------------------
any Stockholder who is an Affiliate of such Stockholder or the spouse, lineal
descendants (natural or adopted) or parents of such Stockholder or Affiliate, or
(with the prior consent of the Corporation, which consent shall not be
unreasonably withheld or delayed) the respective constituent partners or
participants of such Stockholder or such partners' or participants' direct and
indirect constituent partners, stockholders and Affiliates, or an inter vivos
                                                                  ----- -----
trust for the benefit of any such Person or, in the case of the MDCP Group
Stockholders, any other transferee of no more than two percent of the Securities
in the aggregate held by the MDCP Group Stockholders as of February 4, 2000, so
long as such transferee is designated by the MDCP Group Stockholders in writing
to the Corporation as a "Permitted Transferee" promptly following the time of
such transfer.

     1.7  "Person" shall mean any individual, corporation, partnership (general
           ------
or limited), limited liability company, limited liability partnership, firm,
trust, association or other entity.

     1.8  "Principal Stockholders' Agreement" shall mean that certain
           ---------------------------------
Stockholders' Agreement, dated August 13, 1998, among Mr. Chesonis, Mr.
Edgecomb, as Trustee of the Christopher E. Edgecomb Living Trust dated April 25,
1998, and Mr. Sudikoff, as such Stockholders' Agreement is in effect as of the
date hereof.

                                       2
<PAGE>

     1.9  "Public Offering" means any bona fide underwritten sale of the Common
           ---------------
Stock to the public pursuant to an effective registration statement under the
Securities Act of 1933, as amended, filed with the Securities and Exchange
Commission on Form S-1 (or a successor form adopted by the Securities and
Exchange Commission); provided that the following shall not be considered a
Public Offering: (i) any issuance of Common Stock as consideration for a merger
or acquisition; and (ii) any issuance of Common Stock or rights to acquire
Common Stock to existing securityholders or to employees of the Corporation or
its subsidiaries on Form S-4 or Form S-8 (or any successor forms adopted by the
Securities and Exchange Commission) or otherwise.

     1.10 "Securities" shall mean, collectively, all capital stock of the
           ----------
Corporation, all rights to acquire any shares of any capital stock of the
Corporation and all securities convertible into capital stock of the Corporation
(including indebtedness convertible into or exchangeable for shares of capital
stock of the Corporation), together with any and all securities received as
stock splits, dividends on or in substitution for any capital stock of the
Corporation, or in connection with any increase, reduction or reclassification
of the capital stock of the Corporation, or upon any reorganization,
recapitalization, share exchange, exchange offer, merger or consolidation of the
Corporation with any one or more entities in which an entity other than the
Corporation is the surviving entity, or upon the exercise of any option or
warrant to purchase capital stock of the Corporation.

2.   Matters Concerning the Board of Directors.
     -----------------------------------------

     2.1  Composition of the Board. From and after the effectiveness of this
          ------------------------
Agreement and until the provisions of this Section 2 cease to be effective, each
Stockholder shall vote all of such Stockholder's Securities and any other voting
securities of the Corporation over which such Stockholder has voting control and
shall take all other necessary or desirable actions within such Stockholder's
control (whether in the capacity as a stockholder, director, member of a Board
committee or officer of the Corporation or otherwise, and including, without
limitation, attendance at meetings in person or by proxy for purposes of
obtaining a quorum and execution of written consents in lieu of meetings), and
the Corporation shall take all necessary and desirable actions within its
control (including, without limitation, calling special Board and stockholder
meetings and nominating individuals to the Board in accordance with, and not
inconsistent with, the terms and conditions contained herein and in the
Corporation's certificate of incorporation), so that the following persons shall
be elected to the Board:

          (i) CCS Group Directors. Until such date as the CCS Group Stockholders
              -------------------
          (including their Permitted Transferees) cease to beneficially own, on
          an aggregate basis, at least 5% of the Common Stock issued and
          outstanding in the aggregate, the nominees to serve as directors of
          the Corporation nominated by the CCS Group Stockholders (which term,
          for purposes of this Section 2, shall refer to each CCS Group
          Stockholder and each Permitted Transferee of each CCS Group
          Stockholder) (the "CCS Group Directors"), the number of which shall
                             -------------------
          equal the greater of (x) the number of members of the Board multiplied
                    ------- --                                        ----------
          by the CCS Board Percentage, rounded down to the nearest whole number
          --
          and (y) one nominee.  For purposes of this Section 2.1(i), the "CCS
                                                                          ---
          Board Percentage" shall, with respect to any nomination of a CCS Group
          ----------------
          Director,  be equal to the total number of shares

                                       3
<PAGE>

          of Common Stock beneficially owned by the CCS Group Stockholders
          (including their Permitted Transferees) at the time of any such
          nomination of a CCS Group Director divided by the total number of
                                             ------- --
          issued and outstanding shares of Common Stock. For purposes of this
          Section 2.1(i), nominees to serve as CCS Group Directors shall be
          determined by the vote of CCS Group Stockholders beneficially owning a
          majority of the shares of Common Stock held by all the CCS Group
          Stockholders at the time of any such nomination of a CCS Group
          Director.

          (ii) MDCP Group Directors:
               --------------------

                    (A) Prior to a Public Offering.  Prior to the consummation
                        --------------------------
               of a Public Offering, until such date as the holders of the
               Series A Preferred on the date of its initial issuance and the
               Permitted Transferees of such holders beneficially own in the
               aggregate (x) Series A Preferred and (y) shares of Common Stock
               received upon a conversion of the Series A Preferred in
               accordance with the conversion rights set forth in the
               Corporation's certificate of incorporation, which together, on an
               as-converted basis, represent less than one-third of the
               aggregate number of shares of Common Stock issuable upon
               conversion of all of the Series A Preferred acquired by the
               holders of the Series A Preferred on the date of its initial
               issuance, (1) one person nominated by the MDCP Group Stockholders
               if the Board has eight or fewer members, (2) two persons
               nominated by the MDCP Group Stockholders if the Board  has
               between nine and fourteen members, and (3) and three persons
               nominated by the MDCP Group Stockholders if the Corporation has
               fifteen or more members.  Each person elected to the Board
               pursuant to a nomination made in accordance with this clause (A)
               or clause (B) below is referred to herein individually as an
               "MDCP Director" and collectively as the "MDCP Directors".
                -------------                           --------------

                    (B) After a Public Offering.
                        -----------------------

                        1. After a Public Offering, and until such date as the
                        MDCP Group Stockholders and their Permitted Transferees
                        collectively own beneficially in the aggregate (x)
                        Series A Preferred and (y) shares of Common Stock
                        received upon a conversion of the Series A Preferred in
                        accordance with the Corporation's certificate of
                        incorporation, which together, on an as-converted basis,
                        represent less than either (1) one-third of the
                                  ---- ----
                        aggregate number of shares of Common Stock issuable upon
                        conversion of all of the Series A Preferred acquired by
                        the MDCP Group Stockholders on the date of its initial
                        issuance or (2) five percent of the Common Stock issued
                        and outstanding in the aggregate, one person nominated
                        by the MDCP Group Stockholders and their Permitted
                        Transferees; and

                                       4
<PAGE>

                         2.    After a Public Offering, at any time in which the
                         number of members of the Board is established at nine
                         or greater and until the date on which the MDCP Group
                         Stockholders and their Permitted Transferees
                         collectively own beneficially in the aggregate (x)
                         Series A Preferred and (y) shares of Common Stock
                         received upon a conversion of the Series A Preferred in
                         accordance with the Company's certificate of
                         incorporation, which together, on an as-converted
                         basis, represent less than either (1) fifty percent of
                                          ---- ----
                         the aggregate number of shares of Common Stock issuable
                         upon conversion of all of the Series A Preferred
                         acquired  by the MDCP Group Stockholders on the date of
                         its initial issuance or (2) five percent of the Common
                         Stock issued and outstanding in the aggregate, a second
                         person  nominated by the MDCP Group Stockholders and
                         their Permitted Transferees;

                    (C)  Determinations Made by the MDCP Group Stockholders and
                         ------------------------------------------------------
               Their Permitted Transferees.  Nominations and other actions and
               ---------------------------
               determinations made by the MDCP Stockholders and their Permitted
               Transferees under this Agreement shall be made by the MDCP
               Stockholders and their Permitted Transferees holding a majority
               of the shares of Common Stock (calculated on an as-converted
               basis with respect to any Preferred Stock held by such
               Stockholders) beneficially owned  collectively by all of the MDCP
               Stockholders and their Permitted Transferees.

         (iii) Blackstone Group Directors:
               --------------------------

                    (A)  Prior to a Public Offering.  Prior to the consummation
                         --------------------------
               of a Public Offering, until such date as the holders of the
               Series A Preferred on the date of its initial issuance and the
               Permitted Transferees of such holders beneficially own in the
               aggregate (x) Series A Preferred and (y) shares of Common Stock
               received upon a conversion of the Series A Preferred in
               accordance with the conversion rights set forth in the
               Corporation's certificate of incorporation, which together, on an
               as-converted basis, represent less than one-third of the
               aggregate number of shares of Common Stock issuable upon
               conversion of all of the Series A Preferred acquired by the
               holders of the Series A Preferred on the date of its initial
               issuance, (1) one person nominated by the Blackstone Group
               Stockholders if the Board has twelve or fewer than twelve
               members, (2) two persons nominated by the Blackstone Group
               Stockholders if the Board has between twelve and seventeen
               members, and (3) three persons nominated by the Blackstone Group
               Stockholders if the Board has eighteen or more members.  Each
               person elected to the Board pursuant to a nomination made in
               accordance with this clause (A) or clause (B) below is

                                       5
<PAGE>

               referred to herein individually as a "Blackstone Director" and
                                                     -------------------
               collectively as the "Blackstone Directors".
                                    --------------------

                    (B) After a Public Offering.  After a Public Offering, and
                        -----------------------
               until such date as the Blackstone Group Stockholders and their
               Permitted Transferees collectively own beneficially in the
               aggregate (x) Series A Preferred and (y) shares of Common Stock
               received upon a conversion of the Series A Preferred in
               accordance with the Corporation's certificate of incorporation,
               which together, on an as-converted basis, represent less than
                                                                   ---- ----
               either (1) one-third of the aggregate number of shares of Common
               Stock issuable upon conversion of all of the Series A Preferred
               acquired by the Blackstone Group Stockholders on the date of its
               initial issuance or (2) five percent of the Common Stock issued
               and outstanding in the aggregate, one person nominated by the
               Blackstone Group Stockholders and their Permitted Transferees

                    (C) Determinations Made by the Blackstone Group Stockholders
                        --------------------------------------------------------
               and Their Permitted Transferees.  Nominations and other actions
               -------------------------------
               and determinations made by the Blackstone Group Stockholders and
               their Permitted Transferees under this Agreement shall be made by
               the Blackstone Group Stockholders and their Permitted Transferees
               holding a majority of the shares of Common Stock (calculated on
               an as-converted basis with respect to any Preferred Stock held by
               such Stockholders) beneficially owned collectively by all of the
               Blackstone Group Stockholders and their Permitted Transferees.

          (iv) Chesonis Directors:  Until such date as Mr. Chesonis ceases to be
               ------------------
          at least one of the Chairman of the Board or the Chief Executive
          Officer of the Corporation or Mr. Chesonis ceases to beneficially own,
          or otherwise ceases to have the right to vote, any shares of Class B
          Common Stock, other than with respect to any votes required to be
          voted for the CCS Group Directors, the MDCP Directors and the
          Blackstone Directors pursuant to this Section 2, the Stockholders
          shall vote all of their shares of capital stock for the election of
          any other directors nominated by Mr. Chesonis (each, a "Chesonis
                                                                  --------
          Director").
          --------

Notwithstanding Section 2.1(ii)(A) and 2.1(iii)(A), the maximum number of MDCP
Directors and Blackstone Directors in the aggregate at any time prior to the
consummation of a Public Offering shall not exceed the maximum number provided
for in paragraph 5A of the Corporation's Restated Certificate of Incorporation
as of the date hereof (except as provided for in Section 8 of such Restated
Certificate of Incorporation).

          (a)  The removal from the Board of any person nominated to the Board
     pursuant to this Section 2 without cause shall be only upon the written
     request of (1) in the case of any CCS Group Director, the CCS Group
     Stockholders and their Permitted Transferees holding a majority of the
     shares of Common Stock held by all of the CCS Group Stockholders; (2) in
     the case of any MDCP Director, the MDCP Group Stockholders and their
     Permitted Transferees; (3) in the case of any Blackstone Director,

                                       6
<PAGE>

     the Blackstone Group Stockholders and their Permitted Transferees; and (4)
     in the case of a Chesonis Director, by Mr. Chesonis; provided that upon the
                                                          -------- ----
     request of the Investor Stockholders holding a majority of the shares of
     Common Stock (calculated on an as-converted basis with respect to any
     Preferred Stock held by such Stockholders) held by all of the Investor
     Stockholders, Mr. Chesonis shall take such action as is necessary to remove
     the Chesonis Directors at such time, if any, that Mr. Chesonis is no longer
     at least one of the Chairman of the Board or the Chief Executive Officer of
     the Corporation.

          (b) The removal from the Board of any person nominated to the Board
     pursuant to this Section 2 for cause shall be only upon the written request
     of a majority of the shares of Common Stock beneficially owned collectively
     by all of the Stockholders (calculated on an as-nominated basis with
     respect to any Preferred Stock held by such Stockholders).

          (c) In the event that any person designated as a director hereunder
     for any reason ceases to serve as a member of the Board during such
     person's term of office, the resulting vacancy on the Board shall be filled
     by a representative designated by the person or persons entitled to remove
     such director pursuant to Section 2.1(a).

          (d) If, and so long as, any of the MDCP Group Stockholders, the
     Blackstone Group Stockholders or the CCS Group Stockholders fails to
     designate a representative to fill a directorship pursuant to the terms of
     this Section 2, the election of a person to such directorship shall be
     accomplished in accordance with the Corporation's certificate of
     incorporation, bylaws and applicable law.

          (e) The Company shall reimburse each CSC Group Director, each MDCP
     Director and each Blackstone Director for all reasonable out-of-pocket
     expenses borne by such directors in connection with the performance of
     their duties as directors of the Corporation and in connection with their
     attendance at any meeting of the Board.

Each Stockholder shall be obligated to vote such Stockholder's Securities and
take all other actions set forth in Section 2.1 with respect to the election of
any person to the Board only if (i) such Stockholder is entitled under the
Corporation's certificate of incorporation to vote on the election of such
person to the Board and (ii) following such time, if ever, as the Corporation
has a class of equity securities registered under Section 12 of the Securities
Exchange Act of 1934, as amended (the "Exchange Act"), only if compliance with
                                       ------------
Section 2.1 would not, by itself, obligate such Stockholder or its Affiliates to
comply with the requirements of Section 16 of the Exchange Act.

     2.2  Committees of the Board. So long as any MDCP Director or Blackstone
          -----------------------
Director is a member of the Board, one of such directors shall be entitled
hereunder to serve as a member of any committee of the Board which is
established.

3.   Injunctive Relief.  Each Stockholder and the Corporation acknowledges and
agrees that the terms, covenants and obligations of this Agreement relate to
special, unique and extraordinary matters and that a violation of any of the
terms, covenants or obligations of this Agreement will cause the Corporation and
each Stockholder irreparable injury in an amount

                                       7
<PAGE>

which would be impossible to estimate or determine and for which adequate
compensation could not be fashioned. Therefore, each Stockholder and the
Corporation agrees that the Corporation and/or the other Stockholders (as
applicable) will be entitled to an injunction, restraining order or other
equitable relief as a matter of course, and without the necessity of proving
irreparable harm or the inadequacy of a legal remedy or posting a bond, from any
court of competent jurisdiction, restraining the applicable Stockholders or the
Corporation and any other Persons as the court may order from committing any
violation or threatened violation of the terms, covenants or obligations in this
Agreement. The rights and remedies of the Corporation and each Stockholder under
this Section 3 are cumulative and are in addition to any other rights and
remedies that the Corporation or any Stockholder may have under this Agreement
or any other agreement or at law or in equity.

4.   Miscellaneous.
     -------------

     4.1  Continuing Force; Remedies Cumulative.  The provisions contained in
          -------------------------------------
this Agreement will survive and remain in full force and effect after execution
of this Agreement.  The remedies contained in this Agreement will survive and
remain in full force and effect after the termination of this Agreement.  The
rights and remedies provided for in this Agreement are cumulative and will be in
addition to rights and remedies otherwise available to the parties under any
other agreement or applicable law.

     4.2  Amendment.  This Agreement may only be amended by a written agreement
          ---------
signed by (i) the Corporation, (ii) the Principal Stockholders holding a
majority of the Common Stock held collectively by all of the Principal
Stockholders at the time of the proposed amendment, (iii) CCS Group
Stockholders, holding a majority of the Common Stock held collectively by all of
the CCS Group Stockholders at the time of the proposed amendment, (iv) MDCP
Group Stockholders holding a majority of the Common Stock (calculated on an as-
converted basis with respect to any Preferred Stock held by such Stockholders)
held collectively by all of the MDCP Group Stockholders at the time of the
proposed amendment, and (v) the Blackstone Group Stockholders holding a majority
of the Common Stock (calculated on an as-converted basis with respect to any
Preferred Stock held by such Stockholders) held collectively by all of the
Blackstone Group Stockholders at the time of the proposed amendment.

     4.3  Waiver.  No waiver of any Section or provision of this Agreement will
          ------
be enforceable against any party to this Agreement unless set forth in a writing
signed by such party.  Unless such a writing expressly provides otherwise, any
waiving by any party of any Section or provision of this Agreement will not
operate or be construed as a waiver of any subsequent breach of this Agreement
or constitute a course of conduct which may be relied upon to justify any
subsequent breach of this Agreement.

     4.4  Notices.  All notices, demands and other communications called for or
          -------
required by this Agreement shall be in writing and shall be addressed to the
parties at their respective addresses stated below or to such other address as a
party may subsequently designate by written notice to the other parties.
Communications hereunder shall be deemed to have been received (i) upon delivery
in person, (ii) five days after such communication is mailed by U.S. certified
mail, return receipt requested and postage prepaid, (iii) the first business day
after such communication is deposited with a commercial overnight carrier which
provides written verification of delivery,

                                       8
<PAGE>

or (iv) the day of transmission of such communication if sent before 2:00 p.m.
recipient's time by facsimile transmission (with confirmation of receipt)
provided that a copy of such communication is sent on the same day by U.S.
certified mail, return receipt requested and postage prepaid, with an indication
that the original was sent by facsimile and the date of its transmittal.

          If to the Corporation to:

                    PaeTec Corp.
                    290 Woodcliff Drive
                    Fairport, New York 14450
                    Attention: President and Chief Executive Officer
                    Telecopier: (716) 340-2547

          with a copy (which shall not constitute notice) to:

                    Hogan & Hartson L.L.P.
                    8300 Greensboro Drive
                    McLean, Virginia  22102
                    Attention:  Richard J. Parrino, Esq.
                    Telecopier:  (703) 610-6200

or at such other address and to the attention of such other person as the
Corporation may designate by written notice to the Stockholders.  Notices to the
Principal Stockholders shall be addressed to:

                    Arunas A. Chesonis
                    c/o PaeTec Corp.
                    290 Woodcliff Drive
                    Fairport, New York  14450
                    Telecopier:  (716) 340-2547

                    Christopher Edgecomb, Trustee
                     of the Christopher E. Edgecomb Living Trust
                     dated April 25, 1998
                    c/o STAR Telecommunications, Inc.
                    223 East De La Guerra
                    Santa Barbara, California  93101
                    Telecopier: (805) 884-1137

                    Jeffrey Sudikoff
                    P.O. Box 491669
                    Los Angeles, California  90049
                    Telecopier:  (310) 382-3376

                                       9
<PAGE>

or at such other address and to the attention of such other person as the
Principal Stockholders may designate by written notice to the Corporation.
Notices to any MDCP Group Stockholder shall be addressed to:

                    c/o  Madison Dearborn Capital Partners
                    Three First National Plaza, Suite 3800
                    Chicago, Illinois 60670
                    Attention:  James N. Perry, Jr.
                                James H. Kirby
                                Greg Share
                    Telecopier: (312) 895-1001

               with a copy (which shall not constitute notice) to:

                    Kirkland & Ellis
                    200 East Randolph Drive
                    Chicago, IL 60601
                    Attention:  Edward T. Swan, Esq.
                                Jeffrey Seifman, Esq.
                                Michael L. Newquist, Esq.
                    Telecopier: (312) 861-2200

or at such other address and to the attention of such other person as the MDCP
Group Stockholders may designate by written notice to the Corporation and the
other Stockholders.  Notices to any Blackstone Group Stockholder shall be
addressed to:

                    c/o The Blackstone Group
                    345 Park Avenue
                    New York, New York  10154
                    Attention:  Lawrence H. Guffey
                                Michael S. Chae
                    Telecopier: (212) 583-5722

          with a copy (which shall not constitute notice) to:

                    Simpson Thacher & Bartlett
                    425 Lexington Ave.
                    New York, New York  10017-3954
                    Attention:  Wilson Neely, Esq.
                    Telecopier: (212) 455-2502

or at such other address and to the attention of such other person as the
Blackstone Group Stockholders may designate by written notice to the Corporation
and the other Stockholders. Notices to any CCS Group Stockholder shall be
addressed to such Stockholder at the address maintained for such Stockholder in
the Corporation's books and records with a copy (which shall not constitute
notice) to:

                                       10
<PAGE>

                    Kirkland & Ellis
                    200 East Randolph Drive
                    Chicago, IL  60601
                    Attention:  David A. Breach, Esq.
                    Telecopier:  (312) 861-2200

or at such other address and to the attention of such other person as the CCS
Group Stockholders may designate by written notice to the Corporation and the
other Stockholders.  Notices to any other Investor Stockholder or any other
Stockholder made from time to time a party to this Agreement shall be addressed
to such Stockholder at the address maintained for such Stockholder in the
Corporation's books and records.

     4.5  Binding Effect and Assignment.  This Agreement, and the rights and
          -----------------------------
duties under it, will be binding upon and inure to the benefit of (i) the
Corporation, its successors and assigns, and (ii) each Stockholder, its
successors and assigns.  No Stockholder may assign its rights under this
Agreement or delegate its duties hereunder unless such Stockholder both assigns
its rights and delegates its duties hereunder, and the transferring Stockholder
obtains from such transferee an agreement in writing, in a form reasonably
satisfactory to the applicable parties, that such transferee will be bound by
this Agreement and that such Securities shall remain subject to the terms of
this Agreement.  Without the prior written consent of the Corporation, no
Stockholder may assign its rights and duties hereunder other than to Permitted
Transferees of such Stockholder.

     4.6  Governing Law.  The corporate law of Delaware will govern all issues
          -------------
concerning the relative rights of the Corporation and its Stockholders.  All
other issues concerning this Agreement shall be governed by and construed in
accordance with the laws of the State of New York without giving effect to any
choice of law or conflict of law provision or rule (whether of the State of New
York or any other jurisdiction) that would cause the application of the law of
any jurisdiction other than the State of New York.

     4.7  Captions.  Captions to the various Sections in this Agreement are for
          --------
the convenience of the parties only and will not affect the meaning or
interpretation of this Agreement.

     4.8  Enforceability and Interpretation.  It is the desire and intent of the
          ---------------------------------
parties to this Agreement that the terms, provisions, conditions, covenants,
representations, warranties, and remedies contained in this Agreement will be
enforceable to the fullest extent permitted by law.  If any term, provision,
condition, covenant, representation, warranty, or remedy of this Agreement or
the application thereof to any person or circumstances will, to any extent, be
construed to be illegal, invalid, or unenforceable, in whole or in part, then
such terms, provisions, condition, covenant, representation, warranty, or remedy
will be construed in a manner so as to permit its enforceability under the
applicable law to the fullest extent permitted by such law.  In any case, the
remaining terms, provisions, conditions, covenants, representations, warranties,
and remedies of this Agreement or the application thereof to any person or
circumstance, except those which have been held illegal, invalid, or
unenforceable, will remain in full force and effect.

                                       11
<PAGE>

     4.9  Counterparts.  This Agreement may be executed in one or more
          ------------
counterparts, each of which will be deemed an original, but together they will
constitute one and the same instrument.

     4.10 Additional Documents.  Each Stockholder agrees to execute any and all
          --------------------
documents, instruments, certificates and communications deeded to be necessary
or desirable by the Corporation to effectuate or reconfirm the applicability of
this Agreement to any and all future transaction affecting the Corporation, the
Securities, or any Stockholder.

     4.11 Cost of Enforcement.  Any party of this Agreement shall pay to any
          -------------------
other party all fees and expenses (including reasonable fees and expenses of
attorneys) incurred by such other party in enforcing its rights under this
Agreement against such party.

     4.12 Entire Agreement. Except as otherwise expressly set forth herein, this
          ----------------
Agreement and the documents referenced herein embody the complete agreement and
understanding among the parties hereto with respect to the subject matter hereof
and supersede and preempt (to the extent that such agreements are inconsistent
with this Agreement) any prior understandings, agreements or representations by
or among the parties, written or oral, which may have related to the subject
matter hereof in any way.  All such understandings, agreements or
representations will no longer be of any further force or effect (except in the
case of any Stockholder who is a party to or otherwise bound by any other
understanding, agreement or representation not to transfer such Stockholder's
Securities, but only with respect to such understandings, agreements or
representations relating only to the transfer of Securities), and, as of the
date hereof, each Stockholder expressly waives all of such Stockholder's rights
under such understandings, agreements or representations.

                            [signature pages follow]

                                       12
<PAGE>

     IN WITNESS WHEREOF, the parties hereto have executed and delivered this
Voting Agreement with full force and effect as of the day and year first written
above.

                      THE CORPORATION:
                      ---------------

                              PAETEC CORP.

                              By: /s/ Arunas A. Chesonis
                                 ----------------------------------------------
                              Its: CEO, Chairman & President
                                  ---------------------------------------------

                      MDCP GROUP STOCKHOLDERS:
                      -----------------------

                              MADISON DEARBORN CAPITAL PARTNERS III, L.P.

                              By:  Madison Dearborn Partners III, L.P.
                              Its: General Partner

                              By:  Madison Dearborn Partners, LLC
                              Its: General Partner

                              By: /s/ James N. Perry
                                 ----------------------------------------------
                              Its: Managing Director

                              MADISON DEARBORN SPECIAL EQUITY III, L.P.

                              By:  Madison Dearborn Partners III, L.P.
                              Its: General Partner

                              By:  Madison Dearborn Partners, LLC
                              Its: General Partner

                              By: /s/ James N. Perry
                                 ----------------------------------------------
                              Its: Managing Director

                              SPECIAL ADVISORS FUND I, LLC

                              By:  Madison Dearborn Partners III, L.P.
                              Its: Manager

                              By:  Madison Dearborn Partners, LLC
                              Its: General Partner

                              By: /s/ James N. Perry
                                 ----------------------------------------------
                              Its: Managing Director

                [Signature Page to Voting Agreement Continues]
<PAGE>

                        BLACKSTONE GROUP STOCKHOLDERS:
                        -----------------------------

                              BLACKSTONE CCC CAPITAL PARTNERS L.P.

                              By: Blackstone Management Associates III L.L.C.

                              By:  /s/ Lawrence H. Guffy
                                 ----------------------------------------
                              Name:  Lawrence H. Guffy
                                   --------------------------------------
                              Title:  Senior Managing Director
                                    -------------------------------------

                              BLACKSTONE CCC OFFSHORE CAPITAL PARTNERS L.P.

                              By:  Blackstone Management Associates III L.L.C.

                              By:  /s/ Lawrence H. Guffy
                                 ----------------------------------------
                              Name:  Lawrence H. Guffy
                                   --------------------------------------
                              Title:  Senior Managing Director
                                    -------------------------------------

                              Executed as a Deed

                              Witnessed by:

                               /s/  Barbara Frive
                              -------------------------------------------

                              BLACKSTONE FAMILY INVESTMENT PARTNERSHIP III L.P.

                              By:  Blackstone Management Associates III L.L.C.

                              By:  /s/ Lawrence H. Guffy
                                 ----------------------------------------
                              Name:  Lawrence H. Guffy
                                   --------------------------------------
                              Title:  Senior Managing Director
                                    -------------------------------------

                [Signature Page to Voting Agreement Continues]
<PAGE>

                            PRINCIPAL STOCKHOLDERS:
                            ----------------------

                              /s/ Arunas A. Chesonis
                              ---------------------------------------
                              Arunas A. Chesonis

                              CHRISTOPHER E. EDGECOMB LIVING TRUST, dated April
                              25, 1998

                              By: /s/ Christopher Edgecomb
                                 ------------------------------------
                                 Christopher Edgecomb, Trustee

                              /s/ Jeffrey Sudikoff
                              ---------------------------------------
                              Jeffrey Sudikoff

                    CCS GROUP STOCKHOLDERS:
                    ----------------------

                              ALLIANCE CABLETEL HOLDINGS, L.P.

                              By: KOCOM Communications, Inc.

                              By: /s/ James A. Kofalt
                                 ------------------------------------
                                 James A. Kofalt, President

                              KLINE HAWKES CALIFORNIA SBIC, L.P.

                              By: /s/ Frank Kline
                                 ------------------------------------

                              Its:  Chairman
                                  -----------------------------------

                              THE UNION LABOR LIFE INSURANCE CORPORATION
                              SEPARATE ACCOUNT P

                              By: /s/ Joseph Linehan
                                 ------------------------------------

                              Its:  VP-Securities
                                  -----------------------------------

                              /s/ Robert I. Schwartz
                              ---------------------------------------
                              Robert I. Schwartz

                              /s/ Kenneth M. Kiraly
                              ---------------------------------------
                              Kenneth M. Kiraly

                [Signature Page to Voting Agreement Continues]
<PAGE>

                              /s/ Susan F. Kiraly
                              ------------------------------------------
                              Susan F. Kiraly

                              /s/ Richard P. Rizzutti
                              ------------------------------------------
                              Richard P. Rizzutti

                              /s/ Bryant Hopper
                              ------------------------------------------
                              Bryant Hopper

                              /s/ Ronald S. Johnson
                              ------------------------------------------
                              Ronald S. Johnson

                              /s/ Lodwrick Cook
                              ------------------------------------------
                              Lodwrick Cook

                              /s/ Peter Cracovaner
                              ------------------------------------------
                              Peter Cracovaner

                              /s/ Richard Cunningham
                              ------------------------------------------
                              Richard Cunningham

                              /s/ Thomas O. FitzGerald
                              ------------------------------------------
                              Thomas O. FitzGerald

                              /s/ Wendy Foliano
                              ------------------------------------------
                              Wendy Foliano

                              /s/ Joseph Golden
                              ------------------------------------------
                              Joseph Golden

                              /s/ Stephen Mayo
                              ------------------------------------------
                              Stephen Mayo

                              /s/ Karen Sancimino
                              ------------------------------------------
                              Karen Sancimino

                              /s/ Clinton Walker
                              ------------------------------------------
                              Clinton Walker

                [Signature Page to Voting Agreement Continues]
<PAGE>

                            OTHER INVESTOR STOCKHOLDERS:
                            ---------------------------

                              NEWCOURT COMMERCIAL FINANCE CORP.

                              By: /s/ Charles Brown
                                 ----------------------------------------
                              Its: V.P.
                                  ---------------------------------------

                              CARAVELLE INVESTMENT FUND, L.L.C.
                              By:  Caravelle Advisors, L.L.C.
                              Its: Investment Manager and Attorney-in-Fact

                              By: [Signature Illegible]
                                 ----------------------------------------
                              Its: Executive Director

                              UNIONBANCAL EQUITIES, INC.

                              By: /s/ David Bonruhi
                                 ----------------------------------------
                              Its: Vice President      VP
                                 ----------------------------------------

                              ARES LEVERAGED INVESTMENT FUND, L.P.
                              By:  ARES Management, L.P.
                              Its: General Partner

                              By: /s/ J. Serot
                                 ----------------------------------------
                              Its: Vice President
                                 ----------------------------------------

                              ARES LEVERAGED INVESTMENT FUND II, L.P.
                              By:  ARES Management, L.P.
                              Its: General Partner

                              By: /s/ J. Serot
                                 ----------------------------------------
                              Its: Vice President
                                 ----------------------------------------

                  [Final Signature Page to Voting Agreement]<PAGE>

                                                                   Exhibit 10.20

                                                                [EXECUTION COPY]

               AMENDED AND RESTATED REGISTRATION RIGHTS AGREEMENT
               --------------------------------------------------

     THIS AMENDED AND RESTATED REGISTRATION RIGHTS AGREEMENT (this "Agreement"),
                                                                    ---------
dated as of February 4, 2000, by and among PaeTec Corp., a Delaware corporation
(the "Corporation"); Alliance Cabletel Holdings, L.P., a Delaware limited
      -----------
partnership ("Alliance"), Kline Hawkes California SBIC, L.P., a California
              --------
limited partnership ("Kline Hawkes"), The Union Labor Life Insurance Corporation
                      ------------
Separate Account P ("ULLICO"), and the other individuals and/or entities listed
                     ------
on Schedule A hereto (together with Alliance, Kline Hawkes and ULLICO, the "CCS
   ----------                                                               ---
Group Stockholders"); Madison Dearborn Capital Partners III, L.P., a Delaware
------------------
limited partnership ("Madison Dearborn Capital"), Madison Dearborn Special
                      ------------------------
Equity II, L.P., a Delaware limited partnership ("Special Equity"), and Special
                                                  --------------
Advisors Fund I, LLC, a Delaware limited liability company ("Special Advisors,"
                                                             ----------------
and together with Madison Dearborn Capital and Special Equity the "MDCP Group
                                                                   ----------
Stockholders"); Blackstone CCC Capital Partners L.P., a Delaware limited
------------
partnership, Blackstone CCC Offshore Capital Partners L.P., a Cayman Islands
limited partnership, and Blackstone Family Investment Partnership III L.P., a
Delaware limited partnership (collectively the "Blackstone Group Stockholders");
                                                -----------------------------
Ares Leveraged Investment Fund L.P., a Delaware limited partnership, Ares
Leveraged Investment Fund L.P. II, a Delaware limited partnership, Newcourt
Commercial Finance Corporation, a Delaware corporation, and UnionBanCal
Equities, Inc., a California corporation (collectively, the "Other Investor
                                                             --------------
Stockholders").  The Other Investor Stockholders, the MDCP Group Stockholders
------------
and the Blackstone Group Stockholders are referred to in this Agreement as the
"Investor Stockholders."  The Other Investor Stockholders, the MDCP Group
Stockholders, the Blackstone Group Stockholders and the CCS Group Stockholders
are sometimes collectively referred to herein as the "Stockholders" and
                                                      ------------
individually as a "Stockholder."
                   -----------

                                    RECITALS
                                    --------

     WHEREAS, the Corporation is party to an Equity Purchase Agreement (the
"Purchase Agreement") dated as of February 4, 2000 with the Investor
-------------------
Stockholders, pursuant to which the Investor Stockholders will purchase shares
of the Corporation's Series A Convertible Preferred Stock, par value $0.01 per
share (the "Preferred Stock").
            ---------------

     WHEREAS, the Corporation and the CCS Group Stockholders are parties to a
Registration Agreement, dated as of September 9, 1999 (the "Prior Agreement"),
                                                            ---------------
pursuant to which the Corporation granted the CCS Stockholders the registration
rights set forth in the Prior Agreement.

     WHEREAS, in order to induce the Investor Stockholders to enter into the
Purchase Agreement, and as a condition precedent to the obligations of the
parties under the Purchase Agreement, the Corporation and the CCS Group
Stockholders have agreed to amend and restate the Prior Agreement and the
Corporation has agreed to grant the Investor Stockholders the registration
rights set forth herein.
<PAGE>

     WHEREAS, this Agreement is the "Registration Agreement" as defined in the
Purchase Agreement.

     NOW, THEREFORE, in consideration of the premises and the covenants and
agreements contained herein, and for other good and valuable consideration, the
receipt and sufficiency of which are hereby acknowledged, and intending to be
legally bound hereby, the parties hereto hereby agree as follows:

                                   ARTICLE 1

        Shelf Registration for the Benefit of the Investor Stockholders
                         and the CCS Group Stockholders

     Section 1.1  Obligation to File and Maintain.  Upon completion of a public
                  -------------------------------
offering of any shares of common stock of the Corporation (whether pursuant to
an initial public offering by the Corporation or as a result of the MDCP Group
Stockholders, the Blackstone Group Stockholders or the CCS Group Stockholders
exercising their demand registration rights pursuant to Article 2), at any time
after the first anniversary and prior to the third anniversary of the completion
of such public offering (which date of completion shall be deemed to be the
third business day after the date on which the registration statement with
respect to such public offering is declared effective), promptly upon the
written request of the MDCP Group Stockholders Representative, the Blackstone
Group Stockholders Representative or the CCS Group Stockholders Representative,
the Corporation will use its best efforts to file, as promptly as reasonably
possible, with the Securities and Exchange Commission (the "Commission") a
                                                            ----------
registration statement under the Securities Act of 1933, as amended and any
successor thereof, and the rules and regulations thereunder (the "Securities
                                                                  ----------
Act"), for the offering on a continuous or delayed basis in the future (the
---
"Shelf Registration") of all of the Registrable Securities then owned by the
-------------------
Investor Stockholders and the CCS Group Stockholders (including, in the case of
the CCS Group Stockholders, shares of Common Stock acquired by any CCS Group
Stockholder in addition to shares of Common Stock acquired in the Merger and, in
the case of the Investor Stockholders, any shares of Common Stock acquired by
any Investor Stockholder upon conversion of the Preferred Stock and any other
shares of Common Stock acquired by an Investor Stockholder).  The Shelf
Registration shall be on an appropriate form that the Corporation is then
eligible to use and the Shelf Registration and any form of prospectus included
therein or prospectus supplement relating thereto shall reflect such plan of
distribution or method of sale as the MDCP Group Stockholders Representative,
the Blackstone Group Stockholders Representative and the CCS Group Stockholders
Representative may from time to time jointly specify in a written notice to the
Corporation, including the sale of some or all of the Registrable Securities in
a public offering or, if requested by the MDCP Group Stockholders
Representative, the Blackstone Group Representative or the CCS Group
Stockholders Representative, subject to receipt by the Corporation of such
information (including information relating to purchasers) as the Corporation
reasonably may require, the sale of some or all of the Registrable Securities
(i) in a transaction constituting an offering outside the United States which is
exempt from the registration requirements of the Securities Act in which the
Corporation undertakes to effect registration of such Registrable Securities as
soon as possible after the completion of such offering in order to permit such
Registrable Securities to be freely tradeable in the United States, (ii) in a
transaction constituting a private placement under Section 4(2) of

                                       2
<PAGE>

the Securities Act in connection with which the Corporation undertakes to
register such Registrable Securities after the conclusion of such placement to
permit such Registrable Securities to be freely tradeable by the purchasers
thereof, or (iii) in a transaction under Rule 144A of the Securities Act in
connection with which the Corporation undertakes to register such Registrable
Securities after the conclusion of such transaction to permit such Registrable
Securities to be freely tradeable by the purchasers thereof. The Corporation
shall use its best efforts to keep the Shelf Registration continuously effective
for the period beginning on the date on which the Shelf Registration is declared
effective and ending on the first date that there are no Registrable Securities.
During the period during which the Shelf Registration is effective, the
Corporation shall supplement or make amendments to the Shelf Registration, if
required by the Securities Act or if reasonably requested jointly by the MDCP
Group Stockholders Representative, the Blackstone Group Stockholders
Representative and the CCS Group Stockholders Representative or an underwriter
of Registrable Securities, including to reflect any specific plan of
distribution or method of sale, and shall use its reasonable best efforts to
have such supplements and amendments declared effective, if required, as soon as
practicable after filing.

     Section 1.2  Black-Out Periods of the MDCP Group Stockholders, the
                  -----------------------------------------------------
Blackstone Group Stockholders and the CCS Group Stockholders.  Subject to the
------------------------------------------------------------
conditions of this Section 1.2, the Corporation shall have the right,
exercisable on not more than two occasions in the aggregate in any period of 24
months, from time to time (i) to require the Investor Stockholders and the CCS
Group Stockholders not to sell under the Shelf Registration or to suspend the
effectiveness thereof during the period starting with the date 30 days prior to
the Corporation's good faith estimate, as certified in writing by an executive
officer of the Corporation to the MDCP Group Stockholders Representative, the
Blackstone Group Stockholders Representative and the CCS Group Stockholders
Representative, of the proposed date of filing of a registration statement or a
preliminary prospectus supplement relating to an existing shelf registration
statement, in either case, pertaining to an underwritten public offering of
equity securities of the Corporation or debt securities of the Corporation which
are convertible into equity securities of the Corporation for the account of the
Corporation, and ending on the date 90 days following the effective date of such
registration statement or the date of filing of such prospectus supplement, or
(ii) to postpone or suspend (but not for a period exceeding 120 days) the filing
or effectiveness of a registration statement otherwise required to be prepared
and filed by it pursuant to this Article 1, if the Corporation determines, in
its good faith judgment as certified in writing by an executive officer of the
Corporation to the MDCP Group Stockholders Representative, the Blackstone Group
Stockholders Representative and the CCS Group Stockholders Representative, that
such registration and offering or continued effectiveness would interfere with
any material financing, acquisition, disposition, corporate reorganization or
other material transaction involving the Corporation or any of its subsidiaries
or public disclosure thereof would be required prior to the time such disclosure
might otherwise be required, or when the Corporation is in possession of
material information that it deems advisable not to disclose in a registration
statement.

     Section 1.3  Black-Out Periods of the Corporation.  Subject to the
                  ------------------------------------
conditions of this Section 1.3, each of the MDCP Group Stockholders and the CCS
Group Stockholders shall have the right, exercisable on not more than two
occasions in any period of 24 months, and the Blackstone Group Stockholders
shall have the right, exercisable on not more than one occasion

                                       3
<PAGE>

in any period of 24 months, to require the Corporation, by written request
provided by the MDCP Group Stockholders Representative, the Blackstone Group
Stockholders Representative or the CCS Group Stockholders Representative (as the
case may be), not to sell any common equity securities of the Corporation, or
any securities convertible into common equity securities of the Corporation
under any registration statement (other than a registration statement on Form S-
8 or other successor form) or prospectus supplement relating to an existing
shelf registration statement, or to suspend the effectiveness thereof, during
the period starting with the date 20 days prior to the good faith estimate of
the MDCP Group Stockholders Representative, the Blackstone Group Stockholders
Representative or the CCS Group Stockholders Representative (as the case may
be), as certified in writing to the Corporation, of a proposed date of filing of
a preliminary prospectus supplement relating to a Shelf Registration filed
pursuant to Section 1.1, pertaining to an underwritten public offering of
Registrable Securities, and ending on the date 45 days following the date of
filing the final prospectus supplement.

     Section 1.4  Additional Black-Out Periods with Respect to Demand
                  ---------------------------------------------------
Registrations.  In addition to the black-out limitations set forth in Sections
-------------
1.2 and 1.3, (i) the MDCP Group Stockholders holding at least 50% of the
Registrable Securities held by all MDCP Group Stockholders shall have the right,
exercisable on not more than two occasions in connection with any permitted
Demand Registration commenced by the MDCP Group Stockholders pursuant to Article
2 to require the CCS Group Stockholders and the other Investor Stockholders not
to sell any common equity securities of the Corporation under the Shelf
Registration during the period starting with the date 20 days prior to the MDCP
Group Stockholders Representative's good faith estimate, as certified in writing
by the MDCP Group Stockholders Representative to the CCS Group Stockholders and
the other Investor Stockholders, of a proposed initial date of distribution of
Registrable Securities under any such permitted Demand Registration commenced by
the MDCP Group Stockholders and ending on the date 180 days following the date
of such initial distribution (or such earlier date permitted by the
underwriters, if such Demand Registration is underwritten); (ii) the Blackstone
Group Stockholders holding at least 50% of the Registrable Securities held by
all Blackstone Group Stockholders shall have the right, exercisable on not more
than one occasion in connection with any permitted Demand Registration commenced
by the Blackstone Group Stockholders pursuant to Article 2 to require the CCS
Group Stockholders and the other Investor Stockholders not to sell any common
equity securities of the Corporation under the Shelf Registration during the
period starting with the date 20 days prior to the Blackstone Group Stockholders
Representative's good faith estimate, as certified in writing by the Blackstone
Group Stockholders Representative to the CCS Group Stockholders and the other
Investor Stockholders, of a proposed initial date of distribution of Registrable
Securities under any such permitted Demand Registration commenced by the
Blackstone Group Stockholders and ending on the date 180 days following the date
of such initial distribution (or such earlier date permitted by the
underwriters, if such Demand Registration is underwritten); and (iii) the CCS
Group Stockholders shall have the right, exercisable on not more than two
occasions in connection with any permitted Demand Registration commenced by the
CCS Group Stockholders pursuant to Article 2, to require the Investor
Stockholders not to sell any common equity securities of the Corporation under
the Shelf Registration during the period starting with the date 20 days prior to
the CCS Group Stockholders Representative's good faith estimate, as certified in
writing by the CCS Group Stockholders Representative to the Investor
Stockholders, of a proposed initial date of distribution of Registrable
Securities under any such permitted Demand Registration commenced

                                       4
<PAGE>

by the CCS Group Stockholders and ending on the date 180 days following the date
of such initial distribution (or such earlier date permitted by the
underwriters, if such Demand Registration is underwritten).

     Section 1.5  Number of Shelf Registrations.  A Shelf Registration shall be
                  -----------------------------
deemed to have been effected if such registration becomes effective pursuant to
the Securities Act and is kept continuously effective of a period of at least
two years; provided, however, that no Shelf Registration shall be deemed to have
           --------  -------
been effected (or to have been kept continuously effective) if such registration
cannot be used by the Investor Stockholders and the CCS Group Stockholders for
more than 90 days as a result of any stop order, injunction or other order of
the Commission or other government authority or for any other reason other than
an act or omission of either the Investor Stockholders or the CCS Group
Stockholders.

     Section 1.6  Expenses.  Any and all Registration Expenses incurred in
                  --------
connection with any Shelf Registration which may be requested under this Article
1 shall be borne by the Corporation.

     Section 1.7  Selection of Underwriters.  Any and all underwriters or other
                  -------------------------
agents involved in any sale of Registrable Securities pursuant to a registration
statement contemplated by this Article 1 shall include such underwriters or
other agents as shall be selected by the Investor Stockholders and the CCS Group
Stockholders holding at least 50% of the Registrable Securities held
collectively by all Investor Stockholders and CCS Group Stockholders
participating in such sale and approved of by the Corporation, which approval
shall not be unreasonably withheld.  The Corporation shall (together with the
Investor Stockholders and/or the CCS Group Stockholders if legally required)
enter into an underwriting agreement in customary form with the underwriter or
underwriters selected for such underwriting, as well as all other documents
customary in similar offerings, which documents shall be in customary form and
reasonably acceptable to the Corporation, including, without limitation,
underwriting agreements, custody agreements, powers of attorney, and
indemnification agreements.

     Section 1.8  Expiration.  Notwithstanding anything in this Section 1 to the
                  ----------
contrary, none of the MDCP Group Stockholders, the Blackstone Group Stockholders
or the CCS Group Stockholders may exercise the shelf registration rights granted
under this Section 1 in connection with a proposed offering of Registrable
Securities by any such group of Stockholders having a reasonably anticipated
aggregate gross offering price of less than $20,000,000 if at such time (if
ever) such MDCP Group Stockholders, such Blackstone Group Stockholders or such
CCS Group Stockholders, as the case may be, are free to sell their shares of
Common Stock under Rule 144 of the Securities Act, without limitation as to
volume or manner of sale restrictions.

                                   ARTICLE 2

                              Demand Registration

     Section 2.1  Obligation to File and Notify.  The CCS Group Stockholders
                  -----------------------------
shall be entitled to Demand Registrations (as defined below) (A) if the
Corporation does not complete an initial public offering of its Common Stock on
or before September 9, 2000 with gross proceeds from the offering of at least
$25 million and (B) as specified below after the Corporation has

                                       5
<PAGE>

completed an initial public offering of its Common Stock. The Investor
Stockholders shall be entitled to Demand Registrations as specified below at any
time after the completion by the Corporation of an initial public offering of
its Common Stock. Subject to the limitations set forth in the foregoing two
sentences and the other limitations set forth in this Section 2.1, if the
Corporation shall receive from (i) the CCS Group Stockholders holding at least
50% of the Registrable Securities held by all CCS Group Stockholders, (ii) the
MDCP Group Stockholders holding at least 50% of the Registrable Securities held
by all MDCP Group Stockholders, or (iii) the Blackstone Group Stockholders
holding at least 50% of the Registrable Securities held by all Blackstone Group
Stockholders, a written request for the Corporation to effect any registration,
qualification or compliance under the Securities Act with respect to Registrable
Securities held by any such group of Stockholders pursuant to this Section 2
(each, a "Demand Registration"), then, at a time specified in such request,
          -------------------
the Corporation will use best efforts to effect such Demand Registration when
so specified in such request, provided that (x) the CCS Group Stockholders
                              -------- ----
shall only be entitled to request one (1) Demand Registration on Form S-1 or any
similar long-form registration statement (each, a "Long-Form Registration") in
                                                   ----------------------
addition to one (1) Demand Registration that the CCS Group Stockholders may
exercise under clause (A) of the first sentence of this Section 2.1, the MDCP
Group Stockholders shall only be entitled to request two (2) Long-Form
Registrations, and the Blackstone Group Stockholders shall only be entitled to
request one (1) Long-Form Registration and (y) each of the MDCP Group
Stockholders holding at least 50% of the Registrable Securities held by all MDCP
Group Stockholders, the Blackstone Group Stockholders holding at least 50% of
the Registrable Securities held by all Blackstone Group Stockholders and the CCS
Group Stockholders holding at least 50% of the Registrable Securities held by
all CCS Group Stockholders shall be entitled to request an unlimited number of
Demand Registrations on Form S-2 or S-3 or any similar short-form registration
statement (each, a "Short-Form Registration") if available; and provided further
                    -----------------------                     -------- -------
that the Corporation shall have at least 150 days after such request with
----
respect to a Demand Registration (including, without limitation, the execution
of an undertaking to file post-effective amendments, appropriate qualification
under the applicable blue sky or other state securities laws and appropriate
compliance with regulations issued under the Securities Act and any other
governmental requirements or regulations) to effect such Demand Registration in
such manner as would permit or facilitate the sale and distribution of the
Registrable Securities specified in such request. A registration shall not count
as one of the permitted Long-Form Registrations until it has become effective
(unless such Long-Form Registration has not become effective due solely to the
fault of the holders requesting such registration), and a Long-Form Registration
shall not count as one of the permitted Long-Form Registrations unless the
holders of Registrable Securities requesting such Demand Registration are able
to register and sell at least 90% of the Registrable Securities requested to be
included in such registration.

     Section 2.2  Underwriting.  If a MDCP Group Stockholder, a Blackstone Group
                  ------------
Stockholder or a CCS Group Stockholder intends to distribute the Registrable
Securities covered by its request by means of an underwritten public offering,
such Stockholder shall so advise the Corporation.  Any and all underwriters or
other agents involved in any sale of Registrable Securities pursuant to a Demand
Registration shall include such underwriters or other agents as shall be
selected by the MDCP Group Stockholders, the Blackstone Group Stockholders or
the CCS Group Stockholders, as the case may be, requesting such a registration
and approved by the Corporation, which approval shall not be unreasonably
withheld or delayed.  The Corporation shall (together with the MDCP Group
Stockholders, the Blackstone Group Stockholders or the

                                       6
<PAGE>

CCS Group Stockholders, as the case may be, if legally required) enter into an
underwriting agreement in customary form with the underwriter or underwriters
selected for such underwriting, as well as all other documents customary in
similar offerings, which documents shall be in customary form and reasonably
acceptable to the Corporation, including, without limitation, underwriting
agreements, custody agreements, powers of attorney, and indemnification
agreements.

     The Corporation may include in any Demand Registration involving an
underwritten public offering and commenced pursuant to this Article 2 securities
for its own account but only to the extent that, in the reasonable belief of the
managing underwriter of such offering, the inclusion of such securities will not
adversely affect the per share sales price for the Registrable Securities
included pursuant to the request for such Demand Registration (including
Registrable Securities included pursuant to the exercise of piggyback rights
granted to the Investor Stockholders and the CCS Group Stockholders under
Section 3.1), and only if the managing underwriter did not exclude any
Registrable Securities held by any Investor Stockholder or CCS Group Stockholder
and requested to be included in such Demand Registration. If the managing
underwriter in an underwritten public offering commenced in connection with a
Demand Registration advises in writing the Corporation, the Investor
Stockholders and the CCS Group Stockholders that marketing factors require a
limitation of the number of shares of Common Stock to be underwritten and sold
in such offering, the managing underwriter may exclude some or all of shares of
Common Stock to be sold in such offering from such registration, in which event
the shares to be included in such registration shall be allocated pro rata among
                                                                  --- ----
the holders of shares participating in the offering pursuant to registration
rights granted by the Corporation (including any demand registration rights and
piggyback rights), based on the number of shares of Common Stock requested to be
included by each holder in such registration.  If any Investor Stockholder or
CCS Group Stockholder disapproves of the terms of any such underwriting, such
Stockholder may elect to withdraw therefrom by written notice to the Corporation
and the managing underwriter.

     Section 2.3  Black-Out Periods of the Investor Stockholders or the CCS
                  ---------------------------------------------------------
Group Stockholders.  Subject to the conditions of this Section 2.3, the
------------------
Corporation shall have the right, exercisable on not more than one occasion in
any period of 12 consecutive months, to postpone or suspend (but not for a
period exceeding 90 days) the filing or effectiveness of a Demand Registration
otherwise required to be prepared and filed by it pursuant to this Article 2, if
the Corporation determines, in its good faith judgment as certified by CEO, that
such registration and offering or continued effectiveness would interfere with
any material financing, acquisition, disposition, corporate reorganization or
other material transaction involving the Corporation or any of its subsidiaries
or public disclosure thereof would be required prior to the time such disclosure
might otherwise be required, or when the Corporation is in possession of
material information that it deems advisable not to disclose in a registration
statement.

     Section 2.4  Expenses.  Any and all Registration Expenses incurred in
                  --------
connection with any Demand Registration which may be requested under this
Article 2 shall be borne by the Corporation.

     Section 2.5  Non-Subordination.  The Demand Registration rights of the
                  -----------------
Investor Stockholders and the CCS Group Stockholders pursuant to this Article 2
shall not be subordinate

                                       7
<PAGE>

to the registration rights of any other Person, and the Corporation shall not
grant any registration rights to any other Person which are superior to the
registration rights granted to the Investor Stockholders and the CCS Group
Stockholders pursuant to this Article 2.

     Section 2.6  Expiration.  Notwithstanding anything in Section 2.1 to the
                  ----------
contrary, none of the MDCP Group Stockholders, the Blackstone Group Stockholders
or the CCS Group Stockholders may exercise the Demand Registration rights
granted under this Article 2 in connection with a proposed offering of
Registrable Securities by any such group of Stockholders having a reasonably
anticipated aggregate gross offering price of less than $20,000,000 if at such
time (if ever) such MDCP Group Stockholders, such Blackstone Group Stockholders
or such CCS Group Stockholders, as the case may be, are free to sell their
shares of Common Stock under Rule 144 of the Securities Act, without limitation
as to volume or manner of sale restrictions.

                                   ARTICLE 3

                         Piggyback Registration Rights

     Section 3.1  Notification and Inclusion.
                  --------------------------

          (a) If, at any time from time to time after the earlier to occur of
     (i) the date on which the Corporation completes an initial public offering
     of shares of its common stock and (ii) September 9, 2000, the Corporation
     proposes to register any of its equity securities, either for its own
     account or for the account of a security holder or holders and whether
     pursuant to its own initiative, the initiative or request of another Person
     or pursuant to a Demand Registration (other than a registration of
     securities relating solely to employee benefit plans or to effect a merger
     or other reorganization), the Corporation shall promptly give written
     notice of such registration to the Investor Stockholders and the CCS Group
     Stockholders.

          (b) Upon the written request of any Investor Stockholder or CCS Group
     Stockholder given within 10 business days after receipt of a notice
     delivered pursuant to Section 3.1(a), the Corporation shall seek to include
     in such proposed registration such Registrable Securities of such
     Stockholder as such Stockholder shall request be so included and shall use
     its best efforts to cause a registration statement covering all of the
     Registrable Securities of such Stockholder that such Stockholder has
     requested to be registered to become effective under the Securities Act.
     The Corporation shall be under no obligation to complete any registration
     of securities it proposes to make under this Article 3, other than its
     obligation to complete any Demand Registration, subject to the terms and
     conditions set forth in Article 2.  If, at any time after giving written
     notice of its intention to register any securities and prior to the
     effective date of the registration statement filed in connection with such
     registration, the Corporation shall determine for any reason not to
     register or to delay registration of such securities, the Corporation shall
     give written notice of such determination to the Investor Stockholders and
     the CCS Group Stockholders and, thereupon, (i) in the case of a
     determination not to register, the Corporation shall be relieved of its
     obligation to register any Registrable Securities in connection with such
     registration (but not from its obligation to pay the Registration

                                       8
<PAGE>

     Expenses incurred in connection therewith) and (ii) in the case of a
     determination to delay registering, the Corporation shall be permitted to
     delay registering any Registrable Securities for the same period as the
     delay in registering such other securities.

     Section 3.2  Cut-back Provision.  If the registration of which the
                  ------------------
Corporation gives notice pursuant to this Article 3 is for a registered public
offering involving an underwriting, the Corporation shall so advise the
Stockholders as part of the written notice given to the Stockholders pursuant to
this Article 3.  If the managing underwriter in an underwritten public offering
pursuant to which Stockholders are participating pursuant to this Article 3
advises in writing the Corporation and the Stockholders that marketing factors
require a limitation of the number of shares of Common Stock to be underwritten
and sold in such offering, the managing underwriter may exclude some or all of
shares of Common Stock held by the Stockholders to be sold in such offering from
such registration, in which event the shares held by the Stockholders to be
included in such registration shall be allocated pro rata among the holders of
shares held by the Stockholders participating in the offering pursuant to
registration rights granted by the Corporation (including any demand
registration rights and piggyback registration rights), based on the number of
shares of Common Stock requested to be included by each holder in such
registration.  If any Stockholder disapproves of the terms of any such
underwriting, such Stockholder may elect to withdraw therefrom by written notice
to the Corporation and the managing underwriter.

     Section 3.3  Expenses.  The Corporation shall bear and pay all Registration
                  --------
Expenses incurred in connection with any registration of Registrable Securities
pursuant to this Article 3.

     Section 3.4  Duration of Registration Rights.  Each Stockholder shall have
                  -------------------------------
unlimited piggyback registration rights set forth in Section 3.1(a) with respect
to the Registrable Securities held by such Stockholder.

     Section 3.5  Non-Subordination. The piggyback registration rights of the
                  -----------------
Stockholders pursuant to this Article 3 shall not be subordinate to the
registration rights of any other Person, and the Corporation shall not grant any
registration rights to any other Person which are superior to the registration
rights granted to the Stockholders pursuant to this Article 3.

                                   ARTICLE 4

                            Registration Procedures

     Section 4.1  In connection with the filing of any registration statement as
provided in Article 1, 2 or 3, the Corporation shall, as expeditiously as
reasonably practicable:

          (a) prepare and file with the Commission the requisite registration
     statement (including a prospectus therein) to effect such registration and
     use its best efforts to cause such registration statement to become
     effective, provided that before filing such registration statement or any
                -------- ----
     amendments or supplements thereto, the Corporation will furnish to the MDCP
     Group Stockholders Representative, the Blackstone Group Stockholders
     Representative and the CCS Group Stockholders Representative, if
     Registrable Securities held by the MDCP Group Stockholders, the Blackstone
     Group Stockholders or the CCS Group Stockholders, as the case may be, are
     included in such

                                       9
<PAGE>

     registration, copies of all such documents proposed to be filed, which
     documents will be subject to the review of counsel to the MDCP Group
     Stockholders, counsel to the Blackstone Group Stockholders and counsel to
     the CCS Group Stockholders before any such filing is made within ten days
     after receipt of such documents, and the Corporation will comply with any
     reasonable request made by any such counsel to make changes in any
     information contained in such documents relating to the Stockholders;

          (b) prepare and file with the Commission such amendments and
     supplements to such registration statement and the prospectus used in
     connection therewith as may be necessary to maintain the effectiveness of
     such registration and to comply with the provisions of the Securities Act
     with respect to the disposition of all securities covered by such
     registration statement until, in the case of Article 1, the termination of
     the period during which the Shelf Registration is required to be kept
     effective, or, in the case of Articles 2 and 3, the earlier of such time as
     all of such securities have been disposed of and the date which is 120 days
     or 90 days, in the case of Article 2 and Article 3, respectively, after the
     date of initial effectiveness of such registration statement;

          (c) furnish to the Stockholders whose Registrable Securities are
     included in such registration such number of conformed copies of such
     registration statement and of each such amendment and supplement thereto
     (in each case including all exhibits), such number of copies of the
     prospectus contained in such registration statements (including each
     complete prospectus and any summary prospectus) and any other prospectus
     filed under Rule 424 under the Securities Act, in conformity with the
     requirements of the Securities Act, and such other documents, including
     documents incorporated by reference, as such Stockholders may reasonably
     request, but only while the Corporation is required under the provisions
     hereof to cause a registration statement to remain in effect;

          (d) use its best efforts to register and qualify all Registrable
     Securities under such other securities or blue sky laws of such
     jurisdictions as any Stockholder whose Registrable Securities are included
     in such registration shall reasonably request, to take all actions which
     may be reasonably necessary to keep such registration or qualification in
     effect for so long as such registration statement remains in effect, and
     take any other action which may be reasonably necessary or advisable to
     enable such Stockholders to consummate the disposition in such
     jurisdictions of the securities owned by such Stockholders, except that the
                                                                 ------ ----
     Corporation shall not for any such purpose be required to qualify generally
     to do business as a foreign corporation in any jurisdiction wherein it
     would not but for the requirements of this paragraph be obligated to be so
     qualified, or to consent to general service of process in any such
     jurisdiction, or change the composition of its assets to conform with the
     securities laws of any such jurisdiction, or to subject the Corporation to
     any material tax in any such jurisdiction where it is not then so subject;

          (e) cause all Registrable Securities covered by such registration
     statement to be registered with or approved by such other government
     authority as may be reasonably necessary to enable the Stockholders to
     consummate the disposition of such Registrable Securities;

                                       10
<PAGE>

          (f) furnish to any managing underwriter of an underwritten public
     offering, to the extent requested by such managing underwriter, a signed
     counterpart, addressed to the managing underwriter (and the underwriters,
     if any), of

               (i)   an opinion of counsel for the Corporation, dated the
          effective date of such registration statement (and, if such
          registration includes an underwritten public offering, dated the date
          of the closing under the underwriting agreement), reasonably
          satisfactory in form and substance to the managing underwriter, and

               (ii)  to the extent permitted by then applicable rules of
          professional conduct, a "comfort" letter, dated the effective date of
          such registration statement (and, if such registration includes an
          underwritten public offering, dated the date of the closing under the
          underwriting agreement), signed by the independent public accountants
          who have certified the Corporation's financial statements included in
          such registration statement, covering substantially the same matters
          with respect to such registration statement (and the prospectus
          included therein) and, in the case of the accountants' letter, with
          respect to events subsequent to the date of such financial statements,
          all as are customarily covered in opinions of issuer's counsel and in
          accountants' letters delivered to the underwriters in underwritten
          public offerings of securities;

          (g) immediately notify the Stockholders whose Registrable Securities
     are included in such registration at any time when the Corporation becomes
     aware that a prospectus relating thereto is required to be delivered under
     the Securities Act, of the happening of any event as a result of which the
     prospectus included in such registration statement, as then in effect,
     includes an untrue statement of a material fact or omits to state any
     material fact required to be stated therein or necessary to make the
     statements therein not misleading in the light of the circumstances under
     which they were made, and at the request of any such Stockholder promptly
     prepare and furnish to such Stockholder a reasonable number of copies of a
     supplement to or an amendment of such prospectus as may be necessary so
     that, as thereafter delivered to the purchasers of such securities, such
     prospectus shall not include an untrue statement of a material fact or omit
     to state a material fact required to be stated therein or necessary to make
     the statements therein not misleading in the light of the circumstances
     under which they were made;

          (h) comply or continue to comply in all material respects with the
     Securities Act and the Securities Exchange Act of 1934, as amended, and any
     successor thereto, and the rules and regulations thereunder (the "Exchange
                                                                       --------
     Act"), and with all applicable rules and regulations of the Commission, and
     ---
     make available to its security holders, as soon as reasonably practicable,
     an earnings statement covering the period of at least twelve (12) months,
     but not more than eighteen (18) months, beginning with the first full
     calendar month of the first full fiscal quarter after the effective date of
     such registration statement, which earnings statement shall satisfy the
     provisions of Section 11(a) of the Securities Act, and not file any
     amendment or supplement to such registration statement or prospectus upon
     which the Stockholders have not been afforded at least five days to review
     and comment;

                                       11
<PAGE>

          (i) provide a transfer agent and registrar for all Registrable
     Securities covered by such registration statement not later than the
     effective date of such registration statement; and

          (j) list all common stock of the Corporation covered by such
     registration statement on any securities exchange on which any of the
     common stock of the Corporation is then listed.

     Section 4.2  Stockholder Information.  Each Stockholder whose Registrable
                  -----------------------
Securities are included in such registration shall furnish in writing to the
Corporation such information regarding such Stockholder the Registrable
Securities to be sold, the intended method of distribution of such Registrable
Securities, and such other information requested by the Corporation as is
necessary for inclusion in the registration statement relating to such offering
pursuant to the Securities Act.  Such writing shall expressly state that it is
being furnished to the Corporation for use in the preparation of a registration
statement, preliminary prospectus, supplementary prospectus, final prospectus or
amendment or supplement thereto, as the case may be.

                                   ARTICLE 5

                                  Preparation

     Section 5.1.  Stockholder Participation in Preparation.  In connection with
                   ----------------------------------------
the preparation and filing of any registration statement under the Securities
Act in which Registrable Securities held by the MDCP Group Stockholders, the
Blackstone Group Stockholders or the CCS Group Stockholders are included, the
Corporation will give the MDCP Group Stockholders, the Blackstone Group
Stockholders, or the CCS Group Stockholders, as the case may be, the
underwriters of each, if any, and their respective counsel, the opportunity to
participate in the preparation of such registration statement, each prospectus
included therein or filed with the Commission, and each amendment thereof or
supplement thereto, and will give each of them such access to its books and
records and such opportunities to discuss the business of the Corporation with
its officers, its counsel and the independent public accountants who have
certified its financial statements as shall be necessary, in the reasonable
opinion of counsel to the MDCP Group Stockholders, counsel to the Blackstone
Group Stockholders and counsel to the CCS Group Stockholders, to conduct a
reasonable investigation within the meaning of the Securities Act.

                                   ARTICLE 6

                                Indemnification

     Section 6.1.  Indemnification by Corporation.  In the event of any
                   ------------------------------
registration of any Registrable Securities of the Corporation under the
Securities Act, the Corporation will, and hereby does, indemnify and hold
harmless the Stockholders, each Person, if any, who controls any Stockholder
within the meaning of the Securities Act, each other Person who participates as
an underwriter in the offering or sale of such securities and each other Person
who controls any such underwriter within the meaning of the Securities Act,
against any expenses, losses, claims, damages or liabilities (or actions in
respect thereof), joint or several, to which the Stockholders

                                       12
<PAGE>

or their respective controlling Persons, or any such underwriter or its
controlling Persons may become subject under the Securities Act or otherwise,
insofar as such expenses, losses, claims, damages or liabilities (or actions or
proceedings, whether commenced or threatened, in respect thereof) arise out of
or are based upon any untrue statement or alleged untrue statement of any
material fact contained in the registration statement under which such
Registrable Securities were registered under the Securities Act, any preliminary
prospectus, final prospectus or summary prospectus contained therein, or any
amendment or supplement thereto, or any omission or alleged omission to state
therein a material fact required to be stated therein or necessary to make the
statements therein, in the light of the circumstances under which they were
made, not misleading, or any violation by the Corporation of the Securities Act,
the Exchange Act, any state securities law or any rule or regulation promulgated
under such laws applicable to the Corporation in connection with any such
registration, and the Corporation will reimburse the Stockholders and their
respective controlling Persons and each such underwriter and its controlling
Persons for any legal or any other expenses reasonably incurred by them, as such
expenses are incurred, in connection with investigating or defending any such
expense, loss, claim, liability, action or proceedings; provided, however, that
                                                        --------  -------
the Corporation shall not be liable in any such case to the extent that any such
expense, loss, claim, damage or liability (or action or proceeding in respect
thereof) arises out of or is based upon an untrue statement or alleged untrue
statement or omission or alleged omission made in such registration statement,
any such preliminary prospectus, final prospectus, summary prospectus, amendment
or supplement in reliance upon and in conformity with written information
furnished to the Corporation by any Stockholder, specifically stating that it is
for use in the preparation thereof.  Such indemnity shall remain in full force
and effect regardless of any investigation made by or on behalf of the
Stockholders or their respective controlling Persons, or any such underwriter or
its controlling Persons, and shall survive the transfer of such securities by
the Stockholders.

     Section 6.2.  Indemnification by the Stockholders.  In the event of any
                   -----------------------------------
registration of any Registrable Securities of the Corporation under the
Securities Act, the Corporation will require, as a condition to including any
Registrable Securities in any registration statement pursuant to Article 1,
Article 2 or Article 3, that the Corporation shall have received an undertaking
satisfactory to it from the applicable Stockholder to indemnify and hold
harmless (in the same manner and to the same extent as set forth in Section 6.1)
the Corporation, each director of the Corporation, each officer of the
Corporation and each other Person, if any, who controls the Corporation within
the meaning of the Securities Act, and each other Person who participates as an
underwriter in the offering or sale of such securities with respect to any
untrue statement or alleged untrue statement of a material fact in or omission
or alleged omission to state a material fact from such registration statement,
any preliminary prospectus, final prospectus or summary prospectus contained
therein, or any amendment or supplement thereto, if such untrue statement or
alleged untrue statement or omission or alleged omission was made in reliance
upon and in conformity with written information furnished to the Corporation by
such Stockholder, specifically stating that it is for use in the preparation of
such registration statement, preliminary prospectus, final prospectus, summary
prospectus, amendment or supplement; provided that in no event shall any
                                     -------- ----
indemnity provided pursuant hereto by a Stockholder exceed the net proceeds from
the offering received by such Stockholder.  Such indemnity shall remain in full
force and effect regardless of any investigation made by or on behalf of the
Corporation or any such director, officer, or controlling Person and shall
survive the transfer of such securities by any Stockholder.

                                       13
<PAGE>

     Section 6.3.  Procedures.  Promptly after receipt by an indemnified party
                   ----------
of notice of the commencement of any action or proceeding involving a claim
referred to in the preceding Sections of this Article 6, such indemnified party
will, if a claim in respect thereof is to be made against an indemnifying party,
give written notice to the latter of the commencement of such action; provided,
                                                                      --------
however, that the failure of any indemnified party to give notice as provided
-------
herein shall not relieve the indemnifying party of its obligations under the
preceding Sections of this Article 6, except to the extent that the indemnifying
party is actually prejudiced by such failure to give notice.  In case any such
action is brought against an indemnified party, unless in such indemnified
party's reasonable judgment a conflict of interest between such indemnified and
indemnifying parties may exist in respect of such claim, the indemnifying party
shall be entitled to participate in and to assume the defense thereof, jointly
with any other indemnifying party similarly notified to the extent that it may
wish, with counsel reasonably satisfactory to such indemnified party, and after
notice from the indemnifying party to such indemnified party of its election so
to assume the defense thereof, the indemnifying party shall not be liable to the
indemnified party for any legal or other expenses subsequently incurred by the
latter in connection with the defense thereof other than reasonable costs of
investigation.

     Section 6.4.  Other Indemnification.  Indemnification similar to that
                   ---------------------
specified in the preceding Sections of this Article 6 (with appropriate
modifications) shall be given by the Corporation and the Stockholders with
respect to any required registration or other qualification of securities under
any federal or state law or regulation of governmental authority other than the
Securities Act.

     Section 6.5.  Payment.  The indemnification required by this Article 6
                   -------
shall be made by periodic payments of the amount thereof during the course of
the investigation or defense, as and when bills are received or any expense,
loss, claim, damage or liability is incurred.

     Section 6.6.  Contribution.  If, for any reason, the foregoing indemnity is
                   ------------
unavailable, or is insufficient to hold harmless an indemnified party, then the
indemnifying party shall contribute to the amount paid or payable by the
indemnified party as a result of the expense, loss, claim, damage or liability,
(i) in such proportion as is appropriate to reflect the relative fault of the
indemnifying party on the one hand and the indemnified party on the other
(determined by reference to, among other things, whether the untrue or alleged
untrue statement of a material fact or omission relates to information supplied
by the indemnifying party or the indemnified party and the parties' relative
intent, knowledge, access to information and opportunity to correct or prevent
such untrue statement or omission), or (ii) if the allocation provided by clause
(i) above is not permitted by applicable law or provides a lesser sum to the
indemnified party than the amount hereinafter calculated, in the proportion as
is appropriate to reflect not only the relative fault of the indemnifying party
and the indemnified party, but also the relative benefits received by the
indemnifying party on the one hand and the indemnified party on the other, as
well as any other relevant equitable considerations.  No indemnified party
guilty of fraudulent misrepresentation (within the meaning of Section 11(f) of
the Securities Act) shall be entitled to contribution from any indemnifying
party who was not guilty of such fraudulent misrepresentation.

                                       14
<PAGE>

                                   ARTICLE 7

                                   Covenants

     Section 7.1.  Filings and Certifications.  The Corporation will file in a
                   --------------------------
timely manner, information, documents and reports in compliance with the
Exchange Act and will, at its expense, forthwith upon the request of any
Stockholder, deliver to such Stockholder a certificate, signed by the
Corporation's principal financial officer, stating (i) the Corporation's name,
address and telephone number (including area code), (ii) the Corporation's
Internal Revenue Service identification number, (iii) the Corporation's
Commission file number, (iv) the number of shares of common stock of the
Corporation outstanding as shown by the most recent report or statement
published by the Corporation, and (v) whether the Corporation has filed the
reports required to be filed under the Exchange Act for a period of at least 90
days prior to the date of such certificate and in addition has filed the most
recent annual report required to be filed thereunder.  If at any time, following
an initial public offering of the Corporation's Common Stock, the Corporation is
not required to file reports in compliance with either Section 13 or Section
15(d) of the Exchange Act, the Corporation will, at its expense, forthwith upon
the written request of the MDCP Group Stockholders Representative, the
Blackstone Group Stockholders Representative or the CCS Group Stockholders
Representative, make available adequate current public information with respect
to the Corporation within the meaning of paragraph (c)(2) of Rule 144 of the
General Rules and Regulations promulgated under the Securities Act.

                                   ARTICLE 8

                                 Miscellaneous

     Section 8.1.  Registration Matters.
                   --------------------

          (a) If Registrable Securities of any Stockholder are included in any
     registration statement, such Stockholder shall execute and deliver all
     documents reasonably requested by the underwriters of an offering covered
     by such registration statement and any other documents customary in similar
     offerings, which documents shall be in customary form, including, without
     limitation, underwriting agreements, custody agreements, powers of
     attorney, and indemnification agreements, provided that no such documents
                                               -------- ----
     shall have terms more onerous than those sought of any other Person in
     connection with the same transaction.

          (b) Each Stockholder whose Registrable Securities are included in any
     registration statement shall cooperate with the Corporation in connection
     with the preparation of such registration statement, and for so long as the
     Corporation is obligated to file and keep effective the registration
     statement, shall provide to the Corporation, in writing, for use in the
     registration statement, all such information regarding such Stockholder as
     the Corporation may from time to time reasonably request in writing and
     which is required in accordance with the Securities Act.

          (c) During such time as the Corporation may be engaged in a
     distribution, the Corporation shall comply with Regulation M promulgated
     under the Exchange Act.

                                       15
<PAGE>

     Section 8.2.  Counterparts.  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 and delivered to the other party.  Copies of executed counterparts
transmitted by telecopy, telefax or other electronic transmission service shall
be considered original executed counterparts for purposes of this Article 8,
provided receipt of copies of such counterparts is confirmed.

     Section 8.3.  Governing Law.  THIS AGREEMENT SHALL BE GOVERNED BY AND
                   -------------
CONSTRUED IN ACCORDANCE WITH THE LAWS OF THE STATE OF NEW YORK WITHOUT REFERENCE
TO THE CHOICE OF LAW PRINCIPLES THEREOF.

     Section 8.4.  Entire Agreement.  This Agreement (including agreements
                   ----------------
incorporated herein) contains the entire agreement between the parties with
respect to the subject matter hereof and there are no agreements or
understandings between the parties other than those set forth or referred to
herein.  This Agreement is not intended to confer upon any person not a party
hereto, or a successor and assign of such party, any rights or remedies
hereunder.

     Section 8.5.  Notices.  All notices and other communications hereunder
                   -------
shall be sufficiently given for all purposes hereunder if in writing and
delivered personally, sent by documented overnight delivery service or, to the
extent receipt is confirmed, telecopy, telefax or other electronic transmission
service to the appropriate address or number as set forth below.  Notices to the
Corporation shall be addressed to:

                              PaeTec Corp.

                              290 Woodcliff Drive
                              Fairport, New York  14450
                              Attention:  President and Chief Executive Officer
                              Telecopier:  (716) 340-2547

                              with a copy (which shall not constitute notice)
                              to:

                              Hogan & Hartson L.L.P.

                              8300 Greensboro Drive
                              McLean, Virginia  22102
                              Attention:  Richard J. Parrino, Esq.
                              Telecopier:  (703) 610-6200

or at such other address and to the attention of such other person as the
Corporation may designate by written notice to the Stockholders.  Notices to any
Stockholder shall be addressed to such Stockholder at the address maintained for
such Stockholder in the Corporation's books and records with a copy (which shall
not constitute notice) to:

                                       16
<PAGE>

          In the case of any CCS Group Stockholder:

                    Kirkland & Ellis
                    200 East Randolph Drive
                    Chicago, IL  60601
                    Attention:  David A. Breach, Esq.
                    Telecopier:  (312) 861-2200

          In the case of any MDCP Group Stockholder:

                    Kirkland & Ellis
                    200 East Randolph Drive
                    Chicago, IL  60601
                    Attention: Edward T. Swan, Esq.
                               Jeffrey Seifman, Esq.
                               Michael L. Newquist, Esq.
                    Telecopier:  (312) 861-2200

          In the case of any Blackstone Group Stockholder:

                    Simpson Thacher & Bartlett
                    425 Lexington Ave.
                    New York, New York  10017-3954
                    Attention:  Wilson Neely, Esq.
                    Telecopier:  (212) 455-2502

or at such other address and to the attention of such other person as any
Stockholder may designate by written notice to the Corporation.

     Section 8.6.  Assignment.  This Agreement shall be binding upon and inure
                   ----------
to the benefit of the parties hereto and their respective successors.  No party
shall be permitted to assign any of its rights hereunder to any third party,
except that if (i) a Stockholder transfers or pledges any or all of the
------ ----
Registrable Securities held by such Stockholder to a bona fide financial
institution as security for any bona fide indebtedness of any such Stockholder,
the pledgee of such Registrable Securities shall be considered an intended
beneficiary hereof and may exercise all rights of such Stockholder hereunder,
and (ii) each Stockholder shall be permitted to assign such Stockholder's rights
hereunder to any other Person to whom such Stockholder may transfer any capital
stock of the Corporation.

     Section 8.7.  Headings.  The Section headings and other headings contained
                   --------
in this Agreement are inserted for convenience of reference only and will not
affect the meaning or interpretation of this Agreement.

     Section 8.8.  Consent to Amendments.  Except as otherwise expressly
                   ---------------------
provided herein, the provisions of this Agreement may be amended and the
Corporation may take any action herein prohibited, or omit to perform any act
herein required to be performed by it, only if the Corporation has obtained the
written consent of each of (x) the holders of a majority of the Registrable
Securities held by all MDCP Group Stockholders at the time such consent is

                                       17
<PAGE>

requested, (y) the holders of a majority of the Registrable Securities held by
all Blackstone Group Stockholders at the time such consent is requested, and (z)
the holders of a majority of the Registrable Securities held by all CCS Group
Stockholders at the time such consent is requested; provided, that if any such
amendment, modification or waiver would adversely and disproportionately affect
any holder of Registrable Securities relative to any holder or holders of
Registrable Securities voting in favor of such amendment, modification, or
waiver, such amendment, modification or waiver shall also require the written
consent of such holder or holders, as the case may be, of a majority of the
outstanding Registrable Securities held by all holders so adversely affected;
and provided, further, that if any such amendment, modification or waiver is to
a provision in this Agreement that requires a specific vote to take an action
thereunder or to take an action with respect to the matters described therein,
such amendment, modification or waiver shall not be effective unless such vote
is obtained with respect to such amendment, modification or waiver.  No other
course of dealing between the Corporation and the holder of any Registrable
Securities or any delay in exercising any rights hereunder shall operate as a
waiver of any rights of any such holders.  This Agreement may not be amended
without the written consent of the Corporation.

     Section 8.9.  Construction.  For the purposes hereof, (i) words in the
                   ------------
singular shall be held to include the plural and vice versa and words of one
gender shall be held to include the other gender as the context requires, (ii)
the terms "hereof," "herein," and "herewith" and words of similar import shall,
unless otherwise stated, be construed to refer to this Agreement as a whole and
not to any particular provision of this Agreement, and Section, paragraph or
other references are to the Sections, paragraphs, or other references to this
Agreement unless otherwise specified, (iii) the word "including" and words of
similar import when used in this Agreement shall mean "including, without
limitation," unless the context otherwise requires or unless otherwise
specified, (iv) the word "or" shall not be exclusive, and (v) provisions shall
apply, when appropriate, to successive events and transactions.

     This Agreement shall be construed without regard to any presumption or rule
requiring construction or interpretation against the party drafting or causing
any instrument to be drafted.

     Section 8.10.  Severability.  Any provision hereof which is invalid or
                    ------------
unenforceable shall be ineffective to the extent of such invalidity or
unenforceability, without affecting in any way the remaining provisions hereof.

                                   ARTICLE 9

                              Certain Definitions

     As used herein, the following terms shall have the following meanings:

     "Blackstone Group Stockholders Representative" shall mean Blackstone CCC
      --------------------------------------------
Capital Partners L.P. or such Person designated thereby.

     "CCS Group Stockholders Representative" shall mean the Person designated as
      -------------------------------------
such under that certain Agreement dated as of September 9, 1999, among the
Corporation and the CCS Group Stockholders.

                                       18
<PAGE>

     "Common Stock" shall mean the common stock, $0.01 par value per share, of
      ------------
the Corporation, including the Class A Common Stock and the Class B Common Stock
of the Corporation.

     "Corporation Registration Expenses" shall mean the fees and disbursements
      ---------------------------------
of counsel and independent public accountants for the Corporation incurred in
connection with the Corporation's performance of or in compliance with this
Agreement, including the expenses of any special audits or "cold comfort"
                                                            ------------
letters required by or incident to such performance and compliance and any
premiums and other costs of policies of insurance obtained by the Corporation
against liabilities arising out of the sale of any securities.

     "Exchange Act" shall mean the Securities Exchange Act of 1934, as amended,
      ------------
and any successor thereof, and the rules and regulations thereunder.

     "MDCP Group Stockholders Representative" shall mean Madison Dearborn
      --------------------------------------
Capital Partners III L.P.

     "Merger" shall have the meaning set forth in the Prior Agreement.
      ------

     "Person" shall mean any individual, corporation, partnership (general or
      ------
limited), limited liability company, limited liability partnership, firm, trust,
association or other entity.

     "Registrable Securities" shall mean (i) with respect to a CCS Group
      ----------------------
Stockholder, any shares of Common Stock acquired by such CCS Group Stockholder,
including any such shares acquired in addition to the shares of Common Stock
acquired in the Merger, and (ii) with respect to an Investor Stockholder, any
shares of Common Stock acquired or acquirable by such Investor Stockholder,
including any such shares acquired or acquirable by converting shares of
Preferred Stock into shares of Common Stock.  As to any particular Registrable
Securities, once issued such securities shall cease to be Registrable Securities
when (A) a registration statement with respect to the sale of such securities
shall have become effective under the Securities Act and such securities shall
have been disposed of in accordance with such registration statement, (B)  such
securities shall have been sold in accordance with Rule 144 (or any successor
provision) under the Securities Act , (C) such securities have been distributed
without consideration by a holder that is a limited liability company to its
members or investment advisor, or by a holder that is a limited partnership to
its limited partners, and in connection with such distribution, such holder has
notified the Corporation in writing of its election to terminate the status of
such securities as Registrable Securities, or (D) subject to Sections 1.8  and
2.6, the Corporation shall have issued certificates representing such securities
without any legend restricting the transfer thereof under the Securities Act or
applicable state securities laws.

     "Registration Expenses" shall mean the Corporation's Registration Expenses,
      ---------------------
all registration, filing and stock exchange or National Association of
Securities Dealers, Inc. fees, all fees and expenses of complying with
securities or blue sky laws (including the reasonable fees and expenses of
counsel to the Stockholders participating in any transaction involving the
registration of Registrable Securities, as follows:  (i) with respect  to any
Demand Registration, the fees and expenses of a single counsel selected by the
group of Stockholders initiating such Demand Registration in connection with
such transaction, (ii) with respect to the filing of a Shelf

                                       19
<PAGE>

Registration, the fees and expenses of no more than two counsel, one selected by
Stockholders holding at least a majority of the Registrable Securities
participating in such registration, and one selected by Stockholders holding at
least 66.67% of the Registrable Securities participating in such transaction,
and (iii) with respect to any other transactions not otherwise described under
clause (i) or (ii), the fees and expenses of a single counsel selected by a
majority of the Stockholders participating in such transaction), all printing
expenses, messenger and delivery expenses, and any fees and disbursements of
underwriters customarily paid by sellers of securities who are not the issuers
of such securities and all underwriting discounts and commissions and transfer
taxes, if any, other than the discounts, commissions, fees and disbursements of
underwriters or selling agents with respect to the Registrable Securities.

     "Securities Act" shall mean the Securities Act of 1933, as amended, and any
      --------------
successor thereof, and the rules and regulations thereunder.

                                 *  *  *  *  *

                                       20
<PAGE>

     IN WITNESS WHEREOF, the parties hereto have executed and delivered this
Amended and Restated Registration Rights Agreement with full force and effect as
of the day and year first written above.

               THE CORPORATION:
               ---------------

                              PAETEC CORP.

                              By: /s/ Arunas A. Chesonis
                                 ---------------------------------------
                              Its: CEO, Chairman & President
                                  --------------------------------------

               MDCP GROUP STOCKHOLDERS:
               -----------------------

                              MADISON DEARBORN CAPITAL PARTNERS III, L.P.

                              By:  Madison Dearborn Partners III, L.P.
                              Its: General Partner

                              By:  Madison Dearborn Partners, LLC
                              Its: General Partner

                              By: /s/ James N. Perry
                                 ---------------------------------------
                              Its:  Managing Director

                              MADISON DEARBORN SPECIAL EQUITY III, L.P.

                              By:  Madison Dearborn Partners III, L.P.
                              Its: General Partner

                              By:  Madison Dearborn Partners, LLC
                              Its: General Partner

                              By: /s/ James N. Perry
                                 ---------------------------------------
                              Its: Managing Director

                              SPECIAL ADVISORS FUND I, LLC

                              By:  Madison Dearborn Partners III, L.P.
                              Its: Manager

                              By:  Madison Dearborn Partners, LLC
                              Its: General Partner

                              By: /s/ James N. Perry
                                 ---------------------------------------
                              Its:  Managing Director

[Signature Page to Amended and Restated Registration Rights Agreement Continues]
<PAGE>

               BLACKSTONE GROUP STOCKHOLDERS:
               -----------------------------

                              BLACKSTONE CCC CAPITAL PARTNERS L.P.

                              By:  Blackstone Management Associates III L.L.C.

                              By: /s/ Lawrence H. Guffy
                                 -----------------------------------------
                              Name: Lawrence H. Guffy
                                   ---------------------------------------
                              Title: Senior Managing Director
                                    --------------------------------------

                              BLACKSTONE CCC OFFSHORE CAPITAL PARTNERS L.P.

                              By:  Blackstone Management Associates III L.L.C.

                              By: /s/ Lawrence H. Guffy
                                 -----------------------------------------
                              Name: Lawrence H. Guffy
                                   ---------------------------------------
                              Title: Senior Managing Director
                                    --------------------------------------

                              Executed as a Deed

                              Witnessed by:

                              /s/ Barbara Frive
                              --------------------------------------------

                              BLACKSTONE FAMILY INVESTMENT PARTNERSHIP III L.P.

                              By:  Blackstone Management Associates III L.L.C.

                              By: /s/ Lawrence H. Guffy
                                 -----------------------------------------
                              Name: Lawrence H. Guffy
                                   ---------------------------------------
                              Title: Senior Managing Director
                                    --------------------------------------

[Signature Page to Amended and Restated Registration Rights Agreement Continues]
<PAGE>

               CCS GROUP STOCKHOLDERS:
               ----------------------

                              ALLIANCE CABLETEL HOLDINGS, L.P.

                              By:  KOCOM Communications, Inc.

                              By:  /s/ James A. Kofalt
                                 -------------------------------------
                                   James A. Kofalt, President

                              KLINE HAWKES CALIFORNIA SBIC, L.P.

                              By: /s/ Frank Kline
                                 -------------------------------------
                              Its: Chairman
                                  ------------------------------------

                              THE UNION LABOR LIFE INSURANCE CORPORATION
                              SEPARATE ACCOUNT P

                              By: /s/ Joseph Linehan
                                 -------------------------------------
                              Its: VP - Securities
                                  ------------------------------------

                              /s/ Robert I. Schwartz
                              ----------------------------------------
                              Robert I. Schwartz

                              /s/ Kenneth M. Kiraly
                              ----------------------------------------
                              Kenneth M. Kiraly

                              /s/ Susan F. Kiraly
                              ----------------------------------------
                              Susan F. Kiraly

                              /s/ Richard P. Rizzutti
                              ----------------------------------------
                              Richard P. Rizzutti

                              /s/ Bryant Hopper
                              ----------------------------------------
                              Bryant Hopper

                              /s/ Ronald S. Johnson
                              ----------------------------------------
                              Ronald S. Johnson

                              /s/ Lodwrick Cook
                              ----------------------------------------
                              Lodwrick Cook

[Signature Page to Amended and Restated Registration Rights Agreement Continues]
<PAGE>

                              /s/ Peter Cracovaner
                              ----------------------------------------
                              Peter Cracovaner

                              /s/ Richard Cunningham
                              ----------------------------------------
                              Richard Cunningham

                              /s/ Thomas O. FitzGerald
                              ----------------------------------------
                              Thomas O. FitzGerald

                              /s/ Wendy Foliano
                              ----------------------------------------
                              Wendy Foliano

                              /s/ Joseph Golden
                              ----------------------------------------
                              Joseph Golden

                              /s/ Stephen Mayo
                              ----------------------------------------
                              Stephen Mayo

                              /s/ Karen Sancimino
                              ----------------------------------------
                              Karen Sancimino

                              /s/ Clinton Walker
                              ----------------------------------------
                              Clinton Walker

               OTHER INVESTOR STOCKHOLDERS:
               ---------------------------

                              NEWCOURT COMMERCIAL FINANCE CORP.

                              By: /s/ Charles Brown
                                 -------------------------------------
                              Its:  V.P.
                                  ------------------------------------

                              CARAVELLE INVESTMENT FUND, L.L.C.
                              By:  Caravelle Advisors, L.L.C.
                              Its:  Investment Manager and Attorney-in-Fact

                              By: /s/ Jason Block
                                 -------------------------------------
                              Its:  Executive Director

[Signature Page to Amended and Restated Registration Rights Agreement Continues]
<PAGE>

          UNIONBANCAL EQUITIES, INC.

          By: /s/ David Bonruhi
             ----------------------------------------
          Its: Vice President       V.P.
              ---------------------------------------

          ARES LEVERAGED INVESTMENT FUND, L.P.
          By:  ARES Management, L.P.
          Its:  General Partner

          By:  /s/ J. Serot
             ----------------------------------------
          Its:  Vice President
              ---------------------------------------

          ARES LEVERAGED INVESTMENT FUND II, L.P.
          By:  ARES Management II, L.P.
          Its:  General Partner

          By:  /s/ J. Serot
             ----------------------------------------
          Its:  Vice President
              ---------------------------------------

[Signature Page to Amended and Restated Registration Rights Agreement Continues]

Source: [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00007-of-00352.parquet"}, [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00007-of-00352.parquet"}]]