Document:

<PAGE>

                                                                   EXHIBIT 10.57

                          REGISTRATION RIGHTS AGREEMENT

                         Dated as of September 30, 2001

                                     between

                             McLeodUSA INCORPORATED

                                       and

               The Purchasers Listed on the Signature Pages Hereto

                                       1
<PAGE>

          REGISTRATION RIGHTS AGREEMENT, dated as of September 30, 2001, between
McLeodUSA Incorporated, a Delaware corporation (the "Company"), and Forstmann
Little & Co. Subordinated Debt and Equity Management Buyout Partnership-VI,
L.P., a Delaware limited partnership ("MBO-VI"), Forstmann Little & Co.
Subordinated Debt and Equity Management Buyout Partnership-VII, L.P., a Delaware
limited partnership ("MBO-VII"), and Forstmann Little & Co. Equity Partnership-
V, L.P., a Delaware limited partnership ("Equity-V" and, collectively with MBO-
VI and MBO-VII, the "Purchasers").

          WHEREAS, the Company and the Purchasers have entered into an Exchange
Agreement (the "Exchange Agreement"), dated as of September 30, 2001, pursuant
to which simultaneously herewith, (i) MBO-VI and MBO-VII are exchanging an
aggregate of 275,000 shares of the Company's Series B Preferred Stock, par value
$0.01 per share (the "Series B Preferred Stock"), for an aggregate of 275,000
shares of the Company's Series D Preferred Stock, par value $0.01 per share (the
"Series D Preferred Stock"), and (ii) Equity-V is exchanging an aggregate of
125,000 shares of the Company's Series C Preferred Stock, par value $0.01 per
share (the "Series C Preferred Stock" and, collectively with the Series B
Preferred Stock, the "Old Preferred Shares"), for an aggregate of 125,000 shares
of the Company's Series E Preferred Stock, par value $0.01 per share (the
"Series E Preferred Stock" and, collectively with the Series D Preferred Stock,
the "Preferred Shares").

          WHEREAS, as part of, and as consideration for, the exchange by the
Purchasers of the Old Preferred Shares for the Preferred Shares on the date
hereof and from time to time hereafter, the Company agrees to grant to the
Purchasers certain registration and other rights with respect to their shares of
Class A Common Stock.

          WHEREAS, in connection with the acquisition by the Purchasers of
shares of Series B Preferred Stock and Series C Preferred Stock, the Company and
the Purchasers entered into that certain Registration Rights Agreement, dated as
of September 15, 1999 (the "Existing Agreement").

          WHEREAS, the Company and the Purchasers are entering into this
Agreement to replace and supersede the Existing Agreement in its entirety and to
grant to the Purchasers certain registration and other rights with respect to
their Preferred Shares and their shares of Class A Common Stock, as more fully
set forth herein.

          NOW, THEREFORE, the parties hereto agree as follows:

          1.  Definitions.  As used herein, unless the context otherwise
              -----------
requires, the following terms have the following respective meanings:

                                       2
<PAGE>

          "Affiliate" has the meaning ascribed to such term in Rule 12b-2 of the
General Rules and Regulations under the Exchange Act.

          "Certificate of Incorporation" means the Restated Certificate of
Incorporation of the Company, as amended, as it may be amended or restated
hereafter from time to time.

          "Commission" means the Securities and Exchange Commission or any other
Federal agency at the time administering the Securities Act.

          "Common Stock" means any shares of Class A Common Stock of the
Company, now or hereafter authorized to be issued, and any and all securities of
any kind whatsoever of the Company which may be exchanged for or converted into
Class A Common Stock, any and all securities of any kind whatsoever of the
Company which may be issued on or after the date hereof in respect of, in
exchange for, or upon conversion of shares of Class A Common Stock pursuant to a
merger, consolidation, stock split, stock dividend, recapitalization of the
Company or otherwise.

          "Exchange Act" means the Securities Exchange Act of 1934, as amended,
or any similar Federal statute, and the rules and regulations of the Commission
thereunder, all as the same shall be in effect at the time.  Reference to a
particular section of the Exchange Act shall include a reference to the
comparable section, if any, of any such similar Federal statute.

          "Person" means a corporation, an association, a partnership, an
organization, a business, a trust, an individual, or any other entity or
organization, including a government or political subdivision or an
instrumentality or agency thereof.

          "Registrable Securities" means (i) any shares of Common Stock owned by
the Purchasers, (ii) any shares of Common Stock issued or issuable upon the
conversion, exercise or exchange of any Preferred Shares of or any other Common
Stock equivalents at any time held by the Purchasers, and (iii) any shares of
Common Stock issued with respect to the Common Stock referred to in clauses (i)
or (ii) by way of a stock dividend, stock split or reverse stock split or in
connection with a combination of shares, recapitalization, merger, consolidation
or otherwise.  As to any particular Registrable Securities, such securities
shall cease to be Registrable Securities (a) when 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) when such securities shall have been
otherwise transferred or disposed of and new certificates for them not bearing a
legend restricting further transfer shall have been delivered by the Company and
subsequent transfer or distribution of them

                                       3
<PAGE>

shall not require registration of them under the Securities Act, or (c) when
such securities shall have been sold as permitted by, and in compliance with,
the Securities Act.

          "Registration Expenses" means all expenses incident to the
registration and disposition of the Registrable Securities pursuant to Section 2
hereof, including, without limitation, all registration, filing and applicable
national securities exchange fees, all fees and expenses of complying with state
securities or blue sky laws (including fees and disbursements of counsel to the
underwriters or the Purchasers in connection with "blue sky" qualification of
the Registrable Securities and determination of their eligibility for investment
under the laws of the various jurisdictions), all word processing, duplicating
and printing expenses, all messenger and delivery expenses, the fees and
disbursements of counsel for the Company and of its independent public
accountants, including the expenses of "cold comfort" letters or any special
audits required by, or incident to, such registration, all fees and
disbursements of underwriters (other than underwriting discounts and
commissions), all transfer taxes, and all fees and expenses of counsel to the
Purchasers; provided, however, that Registration Expenses shall exclude, and the
            --------  -------
Purchasers shall pay, underwriting discounts and commissions in respect of the
Registrable Securities being registered.

          "Securities Act" means the Securities Act of 1933, as amended, or any
similar Federal statute, and the rules and regulations of the Commission
thereunder, all as the same shall be in effect at the time.  References to a
particular section of the Securities Act shall include a reference to the
comparable section, if any, of any such similar Federal statute.

          2.  Registration Under Securities Act, etc.
              ---------------------------------------

              2.1  Registration on Request.
                   -----------------------

                   (a) Request. At any time or from time to time that the
                       -------
Purchasers are permitted to transfer Registrable Securities under Section 4.12
of the Exchange Agreement, the Purchasers shall have the right to require the
Company to effect the registration under the Securities Act of all or part of
the Registrable Securities, by delivering a written request therefor to the
Company specifying the number of shares of Registrable Securities and the
intended method of distribution. The Company shall (i) use its reasonable best
efforts to effect the registration under the Securities Act (including by means
of a shelf registration pursuant to Rule 415 under the Securities Act if so
requested in such request and if the Company is then eligible to use such a
registration) of the Registrable Securities which the Company has been so
requested to register by the Purchasers, for distribution in accordance with the
intended method of distribution set forth in the written request delivered by
the Purchasers, such registration to be effected as expeditiously as possible
(but in any event within 90 days of receipt of a

                                       4
<PAGE>

written request), and (ii) if requested by the Purchasers, use its reasonable
best efforts to obtain acceleration of the effective date of the registration
statement relating to such registration.

                   (b) Registration of Other Securities. Whenever the Company
                       --------------------------------
shall effect a registration pursuant to this Section 2.1 in connection with an
underwritten offering by the Purchasers of Registrable Securities, no securities
other than Registrable Securities shall be included among the securities covered
by such registration if inclusion of such other securities would result in a
request by the managing underwriters for a reduction in the number of
Registrable Securities requested to be so registered.

                   (c) Registration Statement Form. Registrations under this
                       ---------------------------
Section 2.1 shall be on such appropriate registration form of the Commission as,
subject to clause (a)(i) above, shall be selected by the Company and as shall be
reasonably acceptable to the Purchasers. The Company agrees to include in any
such registration statement all information which, in the opinion of counsel to
the Purchasers and counsel to the Company, is necessary or desirable to be
included therein.

                   (d) Expenses. The Company shall pay all Registration Expenses
                       --------
in connection with any registration requested pursuant to this Section 2.1.

                   (e) Effective Registration Statement. A registration
                       --------------------------------
requested pursuant to this Section 2.1 shall not be deemed to have been effected
(including for purposes of paragraph (h) of this Section 2.1) (i) unless a
registration statement with respect thereto has become effective and has been
kept continuously effective for a period of at least 365 days (or such shorter
period which shall terminate when all the Registrable Securities covered by such
registration statement have been sold pursuant thereto), (ii) if after it has
become effective, such registration is interfered with by any stop order,
injunction or other order or requirement of the Commission or other governmental
agency or court for any reason not attributable to the Purchasers and has not
thereafter become effective, or (iii) if the conditions to closing specified in
the underwriting agreement, if any, entered into in connection with such
registration are not satisfied or waived.

                   (f) Selection of Underwriters. The managing underwriters of
                       -------------------------
each underwritten offering of the Registrable Securities so to be registered
shall be selected by the Purchasers, subject to the Company's approval, which
approval shall not be unreasonably withheld.

                   (g) Right to Withdraw.  If the managing underwriter of any
                       -----------------
underwritten offering shall advise the Purchasers that the Registrable
Securities covered

                                       5
<PAGE>

by the registration statement cannot be sold in such offering within a price
range acceptable to the Purchasers, then the Purchasers shall have the right to
notify the Company in writing that they have determined to withdraw their shares
from the registration statement. In the event of such withdrawal, the request
for registration shall not be counted for purposes of the requests for
registration to which the Purchasers are entitled pursuant to this Section 2.1.

                      (h) Limitations on Registration on Request. The Purchasers
                          --------------------------------------
shall be entitled to require the Company to effect, and the Company shall be
required to effect, three registrations in the aggregate pursuant to this
Section 2.1.

                      (i) Postponement. The Company shall be entitled once in
                          ------------
any six-month period to postpone for a reasonable period of time (but not
exceeding 60 days) (the "Postponement Period") the filing of any registration
statement required to be prepared and filed by it pursuant to this Section 2.1
if the Company determines, in its reasonable judgment, that such registration
and offering would materially interfere with any material financing, corporate
reorganization or other material transaction involving the Company or any
subsidiary, or would require premature disclosure thereof, and promptly gives
the Purchasers written notice of such determination, containing a general
statement of the reasons for such postponement and an approximation of the
anticipated delay. If the Company shall so postpone the filing of a registration
statement, (i) the Company shall use its reasonable best efforts to limit the
delay to as short a period as is practicable and (ii) the Purchasers shall have
the right to withdraw the request for registration by giving written notice to
the Company at any time and, in the event of such withdrawal, such request shall
not be counted for purposes of the requests for registration to which the
Purchasers are entitled pursuant to this Section 2.1.

                2.2  Incidental Registration.
                     -----------------------

                      (a) Right to Include Registrable Securities. If the
                          ---------------------------------------
Company at any time proposes to register any of its securities for the account
of any other stockholder under the Securities Act by registration on Form S-1,
S-2 or S-3 or any successor or similar form(s) (except registrations on any such
Form or similar form(s) solely for registration of securities in connection with
an employee benefit plan or dividend reinvestment plan or a merger or
consolidation) and provided that the Purchasers are permitted to transfer
Registrable Securities under Section 4.12 of the Exchange Agreement, the Company
will each such time give prompt written notice to the Purchasers of its
intention to do so and of the Purchasers' rights under this Section 2.2. Upon
the written request of the Purchasers (which request shall specify the maximum
number of Registrable Securities intended to be disposed of by the Purchasers),
made as promptly as practicable and in any event within 30 days after the
receipt of any such notice (10 days if the Company states in such written notice
or gives telephonic notice to

                                       6
<PAGE>

the Purchasers, with written confirmation to follow promptly thereafter, stating
that (i) such registration will be on Form S-3 and (ii) such shorter period of
time is required because of a planned filing date), the Company shall use its
reasonable best efforts to effect the registration under the Securities Act of
all Registrable Securities which the Company has been so requested to register
by the Purchasers; provided, however, that 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 Company shall determine for any reason not to register or to delay
registration of such securities, the Company shall give written notice of such
determination and its reasons therefor to the Purchasers and (i) in the case of
a determination not to register, shall be relieved of its obligation to register
any Registrable Securities in connection with such registration (but not from
any obligation of the Company to pay the Registration Expenses in connection
therewith), without prejudice, however, to the rights of the Purchasers to
request that such registration be effected as a registration under Section 2.1
and (ii) in the case of a determination to delay registering, shall be permitted
to delay registering any Registrable Securities, for the same period as the
delay in registering such other securities. No registration effected under this
Section 2.2 shall relieve the Company of its obligation to effect any
registration upon request under Section 2.1. The Company will pay all
Registration Expenses in connection with any registration of Registrable
Securities requested pursuant to this Section 2.2.

                      (b) Right to Withdraw. The Purchasers shall have the right
                          -----------------
to withdraw its request for inclusion of its Registrable Securities in any
registration statement pursuant to this Section 2.2 at any time prior to the
execution of an underwriting agreement with respect thereto by giving written
notice to the Company of its request to withdraw.

                      (c) Priority in Incidental Registrations. If the managing
                          ------------------------------------
underwriter of any underwritten offering shall inform the Company by letter of
its belief that the number of Registrable Securities requested to be included in
such registration, when added to the number of other securities to be offered in
such registration, would materially adversely affect such offering, then the
Company shall include in such registration, to the extent of the number and type
which the Company is so advised can be sold in (or during the time of) such
offering without so materially adversely affecting such offering (the "Section
2.2 Sale Amount"), (i) all of the securities proposed by the other stockholders
triggering such incidental registration rights; and (ii) thereafter, to the
extent the Section 2.2 Sale Amount is not exceeded, the Registrable Securities
requested by the Purchasers to be included in such registration pursuant to
Section 2.2(a) and any other securities of the Company requested to be included
in such registration by any holder having the right to include securities on a
pro rata basis, including, in the case where such registration is to be effected
as a result of the exercise by a holder of the

                                       7
<PAGE>

Company's securities of such holder's right to cause such securities to be so
registered, the securities of such holder with the amount of securities of the
Purchasers and each such holder to be included based on the pro rata amount of
shares of Common Stock held, or obtainable by exercise or conversion of other
securities of the Company, by the Purchasers or such holder.

                      (d) Plan of Distribution. Any participation by holders of
                          --------------------
Registrable Securities in a registration by the Company shall be in accordance
with the Company's plan of distribution, provided that the Purchasers shall have
the right to select the co-managing underwriter.

                   2.3 Registration Procedures. If and whenever the Company is
                       -----------------------
required to use its reasonable best efforts to effect the registration of any
Registrable Securities under the Securities Act as provided in Sections 2.1 and
2.2 hereof, the Company shall as expeditiously as possible:

                   (a) prepare and file with the Commission as soon as
          practicable the requisite registration statement to effect such
          registration (and shall include all financial statements required by
          the Commission to be filed therewith) and thereafter use its
          reasonable best efforts to cause such registration statement to become
          effective; provided, however, that before filing such registration
                     --------  -------
          statement (including all exhibits) or any amendment or supplement
          thereto or comparable statements under securities or blue sky laws of
          any jurisdiction, the Company shall as promptly as practicable furnish
          such documents to the Purchasers and each underwriter, if any,
          participating in the offering of the Registrable Securities and their
          respective counsel, which documents will be subject to the review and
          comments of the Purchasers, each underwriter and their respective
          counsel; and provided, further, however, that the Company may
                       --------  -------  -------
          discontinue any registration of its securities which are not
          Registrable Securities at any time prior to the effective date of the
          registration statement relating thereto;

                   (b) notify the Purchasers of the Commission's requests for
          amending or supplementing the registration statement and the
          prospectus, and 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 keep such registration
          statement effective and to comply with the provisions of the
          Securities Act with respect to the disposition of all Registrable
          Securities covered by such registration statement for such period as
          shall be required for the disposition of all of such Registrable
          Securities in accordance with the intended method of distribution
          thereof; provided, that except with respect to any such
                   --------

                                       8
<PAGE>

          registration statement filed pursuant to Rule 415 under the Securities
          Act, such period need not exceed 365 days;

                   (c) furnish, without charge, to the Purchasers and each
          underwriter 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 statement (including each preliminary
          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, as the
          Purchasers and such underwriters may reasonably request;

                   (d) use its reasonable best efforts (i) to register or
          qualify all Registrable Securities and other securities covered by
          such registration statement under such securities or blue sky laws of
          such States of the United States of America where an exemption is not
          available and as the Purchasers or any managing underwriter shall
          reasonably request, (ii) to keep such registration or qualification in
          effect for so long as such registration statement remains in effect,
          and (iii) to take any other action which may be reasonably necessary
          or advisable to enable the Purchasers to consummate the disposition in
          such jurisdictions of the securities to be sold by the Purchasers,
          except that the Company 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
          subsection (d) be obligated to be so qualified or to consent to
          general service of process in any such jurisdiction;

                   (e) use its reasonable best efforts to cause all Registrable
          Securities covered by such registration statement to be registered
          with or approved by such other federal or state governmental agencies
          or authorities as may be necessary in the opinion of counsel to the
          Company and counsel to the Purchasers to consummate the disposition of
          such Registrable Securities;

                   (f) furnish to the Purchasers and each underwriter, if any,
          participating in the offering of the securities covered by such
          registration statement, a signed counterpart of (i) an opinion of
          counsel for the Company, and (ii) a "comfort" letter signed by the
          independent public accountants who have certified the Company's or any
          other entity's financial statements included or incorporated by
          reference in such registration statement, covering substantially the
          same matters with respect to such registration statement (and the
          prospectus included therein) and, in the case

                                       9
<PAGE>

          of the accountants' comfort letter, with respect to events subsequent
          to the date of such financial statements, as are customarily covered
          in opinions of issuer's counsel and in accountants' comfort letters
          delivered to the underwriters in underwritten public offerings of
          securities (and dated the dates such opinions and comfort letters are
          customarily dated);

                   (g) promptly notify the Purchasers and each managing
          underwriter, if any, participating in the offering of the securities
          covered by such registration statement (i) when such registration
          statement, any pre-effective amendment, the prospectus or any
          prospectus supplement related thereto or post-effective amendment to
          such registration statement has been filed, and, with respect to such
          registration statement or any post-effective amendment, when the same
          has become effective; (ii) of any request by the Commission for
          amendments or supplements to such registration statement or the
          prospectus related thereto or for additional information; (iii) of the
          issuance by the Commission of any stop order suspending the
          effectiveness of such registration statement or the initiation of any
          proceedings for that purpose; (iv) of the receipt by the Company of
          any notification with respect to the suspension of the qualification
          of any of the Registrable Securities for sale under the securities or
          blue sky laws of any jurisdiction or the initiation of any proceeding
          for such purpose; (v) at any time when a prospectus relating thereto
          is required to be delivered under the Securities Act, upon discovery
          that, or upon 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 in the case of this clause (v), at the
          request of the Purchasers promptly prepare and furnish to the
          Purchasers and each managing underwriter, if any, participating in the
          offering of the Registrable Securities, 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; and (vi) at
          any time when the representations and warranties of the Company
          contemplated by Section 2.4(a) or (b) hereof cease to be true and
          correct;

                   (h) otherwise comply with all applicable rules and
          regulations of the Commission, and make available to its security
          holders, as soon as

                                       10
<PAGE>

          reasonably practicable, an earnings statement covering the period of
          at least twelve months beginning with the first full calendar month
          after the effective date of such registration statement, which
          earnings statement shall satisfy the provisions of Section 11(a) of
          the Securities Act and Rule 158 promulgated thereunder, and promptly
          furnish to the Purchasers a copy of any amendment or supplement to
          such registration statement or prospectus;

                   (i) provide and cause to be maintained a transfer agent and
          registrar (which, in each case, may be the Company) for all
          Registrable Securities covered by such registration statement from and
          after a date not later than the effective date of such registration;

                   (j) (i) use its reasonable best efforts to cause all
          Registrable Securities covered by such registration statement to be
          listed on the NASDAQ "national market system" or the principal
          securities exchange on which similar securities issued by the Company
          are then listed (if any), if the listing of such Registrable
          Securities is then permitted under the rules of such exchange, or (ii)
          if no similar securities are then so listed, use its reasonable best
          efforts to (x) cause all such Registrable Securities to be listed on a
          national securities exchange or (y) failing that, secure designation
          of all such Registrable Securities as a NASDAQ "national market system
          security" within the meaning of Rule 11Aa2-1 of the Commission or (z)
          failing that, to secure NASDAQ authorization for such shares and,
          without limiting the generality of the foregoing, to arrange for at
          least two market makers to register as such with respect to such
          shares with the National Association of Securities Dealers, Inc.;

                   (k) deliver promptly to counsel to the Purchasers and each
          underwriter, if any, participating in the offering of the Registrable
          Securities, copies of all correspondence between the Commission and
          the Company, its counsel or auditors and all memoranda relating to
          discussions with the Commission or its staff with respect to such
          registration statement;

                   (l) use its reasonable best efforts to obtain the withdrawal
          of any order suspending the effectiveness of the registration
          statement;

                   (m) provide a CUSIP number for all Registrable Securities, no
          later than the effective date of the registration statement; and

                   (n) make available its senior executive officers and chairman
          and otherwise provide reasonable assistance to the underwriters
          (taking into

                                       11
<PAGE>

          account the needs of the Company's business) in their marketing of
          Registrable Securities.

The Company may require the Purchasers to furnish the Company such information
regarding the Purchasers and the distribution of the Registrable Securities as
the Company may from time to time reasonably request in writing.

          The Purchasers agree that upon receipt of any notice from the Company
of the happening of any event of the kind described in paragraph (g)(iii), (iv)
or (v) of this Section 2.3, the Purchasers will, to the extent appropriate,
discontinue their disposition of Registrable Securities pursuant to the
registration statement relating to such Registrable Securities until, in the
case of paragraph (g)(v) of this Section 2.3, their receipt of the copies of the
supplemented or amended prospectus contemplated by paragraph (g)(v) of this
Section 2.3 and, if so directed by the Company, will deliver to the Company (at
the Company's expense) all copies, other than permanent file copies, then in its
possession, of the prospectus relating to such Registrable Securities current at
the time of receipt of such notice.  If the disposition by the Purchasers of
their securities is discontinued pursuant to the foregoing sentence, the Company
shall extend the period of effectiveness of the registration statement by the
number of days during the period from and including the date of the giving of
notice to and including the date when the Purchasers shall have received copies
of the supplemented or amended prospectus contemplated by paragraph (g)(v) of
this Section 2.3; and, if the Company shall not so extend such period, the
Purchasers' request pursuant to which such registration statement was filed
shall not be counted for purposes of the requests for registration to which the
Purchasers are entitled pursuant to Section 2.1 hereof.

              2.4  Underwritten Offerings.
                   ----------------------

                   (a) Requested Underwritten Offerings.  If requested by the
                       --------------------------------
underwriters for any underwritten offering by the Purchasers pursuant to a
registration requested under Section 2.1, the Company shall enter into a
customary underwriting agreement (in the form of underwriting agreement used at
such time by the managing underwriter(s)) with a managing underwriter or
underwriters selected by the Purchasers.  Such underwriting agreement shall be
satisfactory in form and substance to the Purchasers and shall contain such
representations and warranties by, and such other agreements on the part of, the
Company and such other terms as are generally prevailing in agreements of the
managing underwriter(s), including, without limitation, their customary
provisions relating to indemnification and contribution.  The Purchasers shall
be party to such underwriting agreement and may, at their option, require that
any or all of the representations and warranties by, and the other agreements on
the part of, the Company to and for the benefit of such underwriters shall also
be made to and for the benefit of the Purchasers and that any or all of the
conditions precedent to the obligations

                                       12
<PAGE>

of such underwriters under such underwriting agreement be conditions precedent
to the obligations of the Purchasers. The Purchasers shall not be required to
make any representations or warranties to or agreements with the Company or the
underwriters other than representations, warranties or agreements regarding the
Purchasers, their ownership of and title to the Registrable Securities, and
their intended method of distribution; and any liability of the Purchasers to
any underwriter or other person under such underwriting agreement shall be
limited to liability arising from breach of their representations and warranties
and shall be limited to an amount equal to the proceeds (net of expenses and
underwriting discounts and commissions) that they derive from such registration.

                   (b) Incidental Underwritten Offerings. In the case of a
                       ---------------------------------
registration pursuant to Section 2.2 hereof, if the Company shall have
determined to enter into any underwriting agreements in connection therewith,
all of the Registrable Securities to be included in such registration shall be
subject to such underwriting agreements. The Purchasers may, at their option,
require that any or all of the representations and warranties by, and the other
agreements on the part of, the Company to and for the benefit of such
underwriters shall also be made to and for the benefit of the Purchasers and
that any or all of the conditions precedent to the obligations of such
underwriters under such underwriting agreement be conditions precedent to the
obligations of the Purchasers. The Purchasers shall not be required to make any
representations or warranties to or agreements with the Company or the
underwriters other than representations, warranties or agreements regarding the
Purchasers, their ownership of and title to the Registrable Securities, and
their intended method of distribution; and any liability of the Purchasers to
any underwriter or other Person under such underwriting agreement shall be
limited to liability arising from breach of their representations and warranties
and shall be limited to an amount equal to the proceeds (net of expenses and
underwriting discounts and commissions) that they derive from such registration.

              2.5 Preparation; Reasonable Investigation. In connection with the
                  -------------------------------------
preparation and filing of each registration statement under the Securities Act
pursuant to this Agreement, the Company will give the Purchasers, their
underwriters, if any, and their respective counsel, accountants and other
representatives and agents 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 give each of
them such access to its books and records and such opportunities to discuss the
business of the Company with its officers and employees and the independent
public accountants who have certified its financial statements, and supply all
other information reasonably requested by each of them, as shall be necessary or
appropriate, in

                                       13
<PAGE>

the opinion of the Purchasers and such underwriters' respective counsel, to
conduct a reasonable investigation within the meaning of the Securities Act.

              2.6  Indemnification.
                   ---------------

                   (a) Indemnification by the Company. The Company agrees that
                       ------------------------------
in the event of any registration of any Registrable Securities of the Company
under this Registration Rights Agreement the Company shall, and hereby does,
indemnify and hold harmless the Purchasers, their respective directors,
officers, members, partners, agents and affiliates and each other Person who
participates as an underwriter in the offering or sale of such securities and
each other Person, if any, who controls the Purchasers or any such underwriter
within the meaning of the Securities Act, against any losses, claims, damages,
or liabilities, joint or several, to which the Purchasers or any such director,
officer, member, partner, agent or affiliate or underwriter or controlling
person may become subject under the Securities Act or otherwise, insofar as such
losses, claims, damages or liabilities, joint or several (or actions or
proceedings, whether commenced or threatened, in respect thereof), arise out of
or are based upon (i) any untrue statement or alleged untrue statement of any
material fact contained in any registration statement under which such
securities were registered under the Securities Act, any preliminary prospectus,
final prospectus or summary prospectus contained therein, or any amendment or
supplement thereto, (ii) any omission or alleged omission to state therein a
material fact required to be stated therein or necessary to make the statements
therein in light of the circumstances in which they were made not misleading, or
(iii) any violation by the Company of any federal, state or common law rule or
regulation applicable to the Company and relating to action required of or
inaction by the Company in connection with any such registration, and the
Company shall reimburse the Purchasers and each such director, officer, member,
partner, agent or affiliate, underwriter and controlling Person for any legal or
any other expenses reasonably incurred by them in connection with investigating
or defending any such loss, claim, liability, action or proceeding; provided
                                                                    --------
that the Company shall not be liable in any such case to the Purchasers or any
such director, officer, member, partner, agent, affiliate, or controlling person
to the extent that any such loss, claim, damage, liability (or action or
proceeding in respect thereof) or expense 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 Company through an
instrument duly executed by or on behalf of the Purchasers, specifically stating
that it is for use in the preparation thereof. Such indemnity shall remain in
full force regardless of any investigation made by or on behalf of the
Purchasers or any such director, officer, member, partner, agent, affiliate,
underwriter or controlling Person and shall survive the transfer of such
securities by the Purchasers.

                                       14
<PAGE>

                   (b) Indemnification by the Purchasers. As a condition to
                       ---------------------------------
including any Registrable Securities in any registration statement, the Company
shall have received an undertaking reasonably satisfactory to it from the
Purchasers so including any Registrable Securities to indemnify and hold
harmless (in the same manner and to the same extent as set forth in paragraph
(a) of this Section 2.6) the Company, and each director of the Company, each
officer of the Company and each other Person, if any, who controls the Company
within the meaning of the Securities Act, with respect to any statement or
alleged statement in or omission or alleged omission from such registration
statement, any preliminary prospectus, final prospectus or summary prospectus
contained therein, or any amendment or supplement thereto, but only to the
extent such statement or alleged statement or omission or alleged omission was
made in reliance upon and in conformity with written information furnished to
the Company through an instrument duly executed by the Purchasers specifically
stating that it is for use in the preparation of such registration statement,
preliminary prospectus, final prospectus, summary prospectus, amendment or
supplement; provided, however, that the liability of any such indemnifying party
            --------  -------
under this Section 2.6(b) shall be limited to the amount of proceeds (net of
expenses and underwriting discounts and commissions) received by such
indemnifying party in the offering giving rise to such liability. Such indemnity
shall remain in full force and effect, regardless of any investigation made by
or on behalf of the Company or any such director, officer or controlling Person
and shall survive the transfer of such securities by the Purchasers.

                   (c) Notices of Claims, etc. 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 subsections of this Section 2.6,
such indemnified party shall, 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 or proceeding; 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 subsections of this
Section 2.6, except to the extent that the indemnifying party is actually
prejudiced by such failure to give notice, and shall not relieve the
indemnifying party from any liability which it may have to the indemnified party
otherwise than under this Section 2.6. In case any such action or proceeding is
brought against an indemnified party, the indemnifying party shall be entitled
to participate therein and, unless in the opinion of outside counsel to the
indemnified party a conflict of interest between such indemnified and
indemnifying parties may exist in respect of such claim, 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; provided, however, that if the defendants in any such action
                   --------  -------
or proceeding include both the indemnified party and the indemnifying party and
if in the opinion of outside counsel to the indemnified party there may be legal
defenses available to such indemnified party and/or other indemnified

                                       15
<PAGE>

parties which are different from or in addition to those available to the
indemnifying party, the indemnified party or parties shall have the right to
select separate counsel to defend such action or proceeding on behalf of such
indemnified party or parties, provided, however, that the indemnifying party
                              --------  -------
shall be obligated to pay for only one counsel and one local counsel for all
indemnified parties. After notice from the indemnifying party to such
indemnified party of its election so to assume the defense thereof and approval
by the indemnified party of such counsel, the indemnifying party shall not be
liable to such indemnified party for any legal expenses subsequently incurred by
the latter in connection with the defense thereof other than reasonable costs of
investigation (unless the first proviso in the preceding sentence shall be
applicable). No indemnifying party shall be liable for any settlement of any
action or proceeding effected without its written consent. No indemnifying party
shall, without the consent of the indemnified party, consent to entry of any
judgment or enter into any settlement which does not include as an unconditional
term thereof the giving by the claimant or plaintiff to such indemnified party
of a release from all liability in respect to such claim or litigation.

                   (d) Contribution. If the indemnification provided for in this
                       ------------
Section 2.6 shall for any reason be held by a court to be unavailable to an
indemnified party under subsection (a) or (b) hereof in respect of any loss,
claim, damage or liability, or any action in respect thereof, then, in lieu of
the amount paid or payable under subsection (a) or (b) hereof, the indemnified
party and the indemnifying party under subsection (a) or (b) hereof shall
contribute to the aggregate losses, claims, damages and liabilities (including
legal or other expenses reasonably incurred in connection with investigating the
same), (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,
with respect to the statements or omissions which resulted in such loss, claim,
damage or liability, or action in respect thereof, as well as any other relevant
equitable considerations, or (ii) if the allocation provided by clause (i) above
is not permitted by applicable law or if the allocation provided in this clause
(ii) provides a greater amount to the indemnified party than clause (i) above,
in such proportion as shall be appropriate to reflect not only the relative
fault but also the relative benefits received by the indemnifying party and the
indemnified party from the offering of the securities covered by such
registration statement as well as any other relevant equitable considerations.
The parties hereto agree that it would not be just and equitable if
contributions pursuant to this Section 2.6(d) were to be determined by pro rata
allocation or by any other method of allocation which does not take into account
the equitable considerations referred to in the preceding sentence of this
Section 2.6(d). No Person guilty of fraudulent misrepresentation (within the
meaning of Section 11(f) of the Securities Act) shall be entitled to
contribution from any Person who was not guilty of such fraudulent
misrepresentation. In addition, no Person shall be obligated to contribute
hereunder any amounts in payment for any settlement of any action or claim
effected without such

                                       16
<PAGE>

Person's consent, which consent shall not be unreasonably withheld.
Notwithstanding anything in this subsection (d) to the contrary, no indemnifying
party (other than the Company) shall be required to contribute any amount in
excess of the proceeds (net of expenses and underwriting discounts and
commissions) received by such party from the sale of the Registrable Securities
in the offering to which the losses, claims, damages or liabilities of the
indemnified parties relate.

                      (e) Other Indemnification. Indemnification and
                          ---------------------
contribution similar to that specified in the preceding subsections of this
Section 2.6 (with appropriate modifications) shall be given by the Company and
the Purchasers with respect to any required registration or other qualification
of securities under any federal, state or blue sky law or regulation of any
governmental authority other than the Securities Act. The indemnification
agreements contained in this Section 2.6 shall be in addition to any other
rights to indemnification or contribution which any indemnified party may have
pursuant to law or contract and shall remain operative and in full force and
effect regardless of any investigation made by or on behalf of any indemnified
party and shall survive the transfer of any of the Registrable Securities by the
Purchasers.

                      (f) Indemnification Payments. The indemnification and
                          ------------------------
contribution required by this Section 2.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 expense, loss, damage or liability is incurred.

                   2.7 Unlegended Certificates. In connection with the offering
                       -----------------------
of any Registrable Securities registered pursuant to this Section 2, the Company
shall (i) facilitate the timely preparation and delivery to the Purchasers and
the underwriters, if any, participating in such offering, of unlegended
certificates representing ownership of such Registrable Securities being sold in
such denominations and registered in such names as requested by the Purchasers
or such underwriters and (ii) instruct any transfer agent and registrar of such
Registrable Securities to release any stop transfer orders with respect to any
such Registrable Securities.

                   2.8 Limitation on Sale of Securities. The Company hereby
                       --------------------------------
agrees that if it shall previously have received a request for registration
pursuant to Section 2.1 or 2.2 hereof, and if such previous registration shall
not have been withdrawn or abandoned, the Company shall not effect any public or
private offer, sale or distribution of its securities or effect any registration
of any of its equity securities under the Securities Act whether or not for sale
for its own account, until a period of 90 days (or such shorter period as the
Purchasers shall be advised by their managing underwriter) shall have elapsed
from the effective date of such previous registration, and the Company shall so
provide in any registration rights agreements hereafter entered into with
respect to any of its securities provided, however, that during this 90 day
period the Company may

                                       17
<PAGE>

(i) offer, sell and distribute its equity securities in connection with
acquisitions or any Company employee or director benefit or stock purchase or
stock option plans, (ii) grant or award Common Stock, options to purchase Common
Stock in connection with acquisitions or under such Company plans and (iii) take
any other actions necessary in connection with any of the foregoing in order to
register such Common Stock with the Commission.

                   2.9 No Required Sale. Nothing in this Agreement shall be
                       ----------------
deemed to create an independent obligation on the part of the Purchasers to sell
any Registrable Securities pursuant to any effective registration statement.

          3.  Rule 144.  Without limiting in any way the provisions of Section
              --------
4.12 of the Exchange Agreement, the Company shall take all actions reasonably
necessary to enable holders of Registrable Securities to sell such securities
without registration under the Securities Act within the limitation of the
exemptions provided by (i) Rule 144, or (ii) any similar rule or regulation
hereafter adopted by the Commission including, without limiting the generality
of the foregoing, filing on a timely basis all reports required to be filed by
the Exchange Act.  Upon the request of the Purchasers, the Company will deliver
to such holder a written statement as to whether it has complied with such
requirements.

          4.  Amendments and Waivers.  This Agreement may be amended, modified
              ----------------------
or supplemented only by written agreement of the party against whom enforcement
of such amendment, modification or supplement is sought.

          5.  [INTENTIONALLY OMITTED]

          6.  Notice.  All notices and other communications hereunder shall be
              ------
in writing and, unless otherwise provided herein, shall be deemed to have been
given when received by the party to whom such notice is to be given at its
address set forth below, or such other address for the party as shall be
specified by notice given pursuant hereto:

         (a)  If to the Purchasers, to:

              c/o Forstmann Little & Co.
              767 Fifth Avenue
              New York, NY  10153
              Attention:  Thomas H. Lister

              With a copy to:

              Fried, Frank, Harris, Shriver & Jacobson
              One New York Plaza

                                       18
<PAGE>

              New York, New York  10004
              Attention:  Robert C. Schwenkel, Esq.

         (b)  If to the Company, to it at:

              McLeodUSA Incorporated
              McLeodUSA Technology Park
              6400 C Street SW
              PO Box 3177
              Cedar Rapids, Iowa  52406-3177
              Telecopy No.:  (319) 790-7901
              Attention:  Randall Rings, Esq.
                       Group Vice President and Chief Legal Officer

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

              Hogan & Hartson L.L.P.
              Columbia Square
              555 Thirteenth Street, N.W.
              Washington, D.C.  20004
              Telecopy No.:  (202) 637-5910
              Attention:  Joseph G. Connolly, Jr., Esq.

          7.  Assignment; Third Party Beneficiaries.  This Agreement shall be
              -------------------------------------
binding upon and inure to the benefit of and be enforceable by the parties
hereto and their respective successors and permitted assigns.  This Agreement
may not be assigned by the Company, without the prior written consent of the
Purchasers.  This Agreement may not be assigned by any of the Purchasers,
without the prior written consent of the Company; provided however, the
Purchasers may, at their election, at any time or from time to time, assign
their rights under this Agreement, in whole or in part, to any Affiliates of the
Purchasers; provided further, however, that any rights to withdraw shares from
inclusion in a registration statement pursuant to Section 2 shall be made only
by the Purchasers for themselves and all such Affiliates.

          8.  Remedies.  The parties hereto agree that money damages or other
              --------
remedy at law would not be sufficient or adequate remedy for any breach or
violation of, or a default under, this Agreement by them and that, in addition
to all other remedies available to them, each of them shall be entitled to an
injunction restraining such breach, violation or default or threatened breach,
violation or default and to any other equitable relief, including without
limitation specific performance, without bond or other security being required.
In any action or proceeding brought to enforce any provision of this

                                       19
<PAGE>

Agreement (including the indemnification provisions thereof), the successful
party shall be entitled to recover reasonable attorneys' fees in addition to its
costs and expenses and any other available remedy.

          9.  No Inconsistent Agreements.  The Company will not, on or after the
              --------------------------
date of this Agreement, enter into any agreement with respect to its securities
which is inconsistent with the rights granted to the Purchasers in this
Agreement or otherwise conflicts with the provisions hereof.  The Company
further represents and warrants that the rights granted to the Purchasers
hereunder do not in any way conflict with and are not inconsistent with any
other agreements to which the Company is a party or by which it is bound.  The
Company further agrees that if any other registration rights agreement entered
into after the date of this Agreement with respect to any of its securities
contains terms which are more favorable to, or less restrictive on, the other
party thereto than the terms and conditions contained in this Agreement are
(insofar as they are applicable) with respect to the Purchasers, then the terms
and conditions of this Agreement shall immediately be deemed to have been
amended without further action by the Company or the Purchasers so that the
Purchasers shall be entitled to the benefit of any such more favorable or less
restrictive terms or conditions.

          10.  Descriptive Headings.  The descriptive headings of the several
               --------------------
sections and paragraphs of this Agreement are inserted for reference only and
shall not control or otherwise affect the meaning hereof.

          11.  Governing Law.  This Agreement shall be construed and enforced in
               -------------
accordance with, and the rights and obligations of the parties hereto shall be
governed by, the laws of the State of New York, without giving effect to the
conflicts of law principles thereof.  Each of the parties hereto hereby
irrevocably and unconditionally consents to submit to the exclusive jurisdiction
of the courts of the State of New York and the United States of America located
in the County of New York for any action or proceeding arising out of or
relating to this Agreement and the transactions contemplated hereby (and agrees
not to commence any action or proceeding relating thereto except in such
courts), and further agrees that service of any process, summons, notice or
document by U.S. registered mail to its respective address set forth in Section
6 hereof shall be effective service of process for any action or proceeding
brought against it in any such court.  Each of the parties hereto hereby
irrevocably and unconditionally waives any objection to the laying of venue of
any action or proceeding arising out of this Agreement or the transactions
contemplated hereby in the courts of the State of New York or the United States
of America located in the County of New York, and hereby further irrevocably and
unconditionally waives and agrees not to plead or claim in any such court that
any such action or proceeding brought in any such court has been brought in an
inconvenient forum.

                                       20
<PAGE>

          12.  Counterparts.  This Agreement may be executed in any number of
               ------------
counterparts, each of which shall be deemed an original, but all such
counterparts shall together constitute one and the same instrument.

          13.  Invalidity of Provision.  The invalidity or unenforceability of
               -----------------------
any provision of this Agreement in any jurisdiction shall not affect the
validity or enforceability of the remainder of this Agreement in that
jurisdiction or the validity or enforceability of this Agreement, including that
provision, in any other jurisdiction.  If any restriction or provision of this
Agreement is held unreasonable, unlawful or unenforceable in any respect, such
restriction or provision shall be interpreted, revised or applied in a manner
that renders it lawful and enforceable to the fullest extent possible under law.

          14.  Further Assurances.  Each party hereto shall do and perform or
               ------------------
cause to be done and performed all further acts and things and shall execute and
deliver all other agreements, certificates, instruments, and documents as any
other party hereto reasonably may request in order to carry out the intent and
accomplish the purposes of this Agreement and the consummation of the
transactions contemplated hereby.

          15.  Termination of Existing Agreement; Entire Agreement;
               ----------------------------------------------------
Effectiveness.  This Agreement replaces and supersedes in its entirety the
-------------
Existing Agreement.  The Existing Agreement is hereby terminated and shall be of
no further force and effect.  Each party hereto agrees and confirms that there
are no unsatisfied obligations of any of the parties hereto under the Existing
Agreement.  This Agreement constitutes the entire agreement, and supersedes all
prior agreements and understandings, oral and written, between the parties
hereto with respect to the subject matter hereof.

                                       21
<PAGE>

          IN WITNESS WHEREOF, the parties have caused this Agreement to be
executed and delivered by their respective officers thereunto duly authorized.

                             McLEODUSA INCORPORATED

                             By:
                                  ---------------------------------
                                  Name:
                                  Title:

                             FORSTMANN LITTLE & CO. EQUITY PARTNERSHIP-V, L.P.

                             By:  FLC XXX Partnership, L.P.
                                  its general partner

                             By:
                                  ---------------------------------
                                  Winston W. Hutchins,
                                  a general partner

                             FORSTMANN LITTLE & CO.
                             SUBORDINATED DEBT AND EQUITY
                             MANAGEMENT BUYOUT PARTNERSHIP-
                             VI, L.P.

                             By:  FLC XXIX Partnership, L.P.
                                  its general partner

                             By:
                                  ---------------------------------
                                  Winston W. Hutchins,
                                  a general partner

                                       22
<PAGE>

                             FORSTMANN LITTLE & CO.
                             SUBORDINATED DEBT AND EQUITY
                             MANAGEMENT BUYOUT PARTNERSHIP-
                             VII, L.P.

                             By:  FLC XXXIII Partnership, L.P.
                                  its general partner

                                  By:
                                     ---------------------------------
                                     Winston W. Hutchins,
                                     a general partner

                                       23<PAGE>

                                                                   EXHIBIT 10.58

                            FULL SERVICES AGREEMENT

     This Agreement is made by McLeodUSA, and Prodigy, effective July 1, 2001
("Effective Date").  McLeodUSA and Prodigy may also be referred to as the
"Parties" or "Party" as the context allows.

In consideration of the mutual promises contained in this Agreement and other
good and valuable consideration, the Parties agree as follows:

1.   Purpose.    The following terms and conditions apply to the provision and
--   --------
use of Services provided to Prodigy by McLeodUSA as the primary provider of
Services as described in any attached addenda, exhibits, schedules and other
documents which are specifically made a part of the Agreement. The Agreement
replaces all prior agreements and understandings, whether written or oral, and
specifically the Full Service Agreement, dated June 24, 1997, the Transition
Services Agreement, dated June 24, 1997, and the Sublease Agreement, dated June
24, 1997. The Agreement Amendment for Internet Access Service Interconnection
between Prodigy Internet Services, Inc., and Splitrock dated May 31, 2000 (GSP
Amendment), as amended on July 10, 2000 (now Exhibit A to this Agreement), the
Second Agreement Amendment for Special 800 Number Service dated May 30, 2000
between Prodigy Communications Corporation and Splitrock Services, Inc. (now
Exhibit B to this Agreement), the Third Amendment between Prodigy Communications
Corporation, and Splitrock Services, Inc., dated July 10, 2000 (now Exhibit C to
this Agreement), and the May 3, 2000 letter agreement concerning prices for OC-3
connections for Prodigy's Yorktown Heights data center as provided for in
Section 28, remain in full force and effect. McLeodUSA will become Prodigy's
preferred nationwide dial access provider exclusive of Prodigy's agreements with
Southwestern Bell Corporation, provided that acceptable network performance is
maintained as required by the Agreement.

2.   Defined Terms.    The following terms are used as defined. The definitions
--   --------------
apply not only to this document but to any referenced or incorporated
attachments .

"Agreement," means this document titled Full Services Agreement and any attached
addenda, exhibits, schedules or other documents specifically referred to and
incorporated.

"End User," means a subscriber services provided by Prodigy, that are supported
by this Agreement, including services where Prodigy is the retailer or wholesale
provider of such services.

"Equipment," means a machine, including its features, conversions, upgrades,
elements, or accessories, or any combination of them.  Equipment includes all
McLeodUSA Equipment either owned or provided by McLeodUSA.  This term excludes
Programs.

"Materials," means work products (such as programs, program listings,
programming tools, documentation, reports, and drawings) that we may deliver to
you during a project.  This term does not include Programs.

"McLeodUSA," means McLeodUSA Information Services, Inc., and any references to
Splitrock or Splitrock Services, Inc.

                                       1
<PAGE>

"NAP," means a Network Access Point.

"POP," means a McLeodUSA point of presence.

"Prodigy," means Prodigy Communications Limited Partnership, and any reference
to Prodigy Communications Corporation or Prodigy Internet Services, Inc.

"Product," means a Program or Equipment.

"Program," means the following, including features and any whole or partial
copies:  (a) machine-readable instructions; (b) a collection of machine-readable
data, such as a database; and (c) related licensed materials, including
documentation and listings, in any form.  The term "Program" includes a
McLeodUSA Program and any non-McLeodUSA Program that McLeodUSA may provide to
you.  The term does not include licensed internal code or Materials.

"Services," means the network services we will provide, as more particularly
described in Section 23 of this Agreement.  Any new or additional service not
contemplated by this Agreement will not be a part of this Agreement until the
terms, conditions, and prices of the service are confirmed in a Transaction
Document.  Services provided to you under this Agreement shall include reports,
surveys and analysis reasonably required to fulfill the purposes of this
Agreement, which shall not be subject to any additional charge.

"System," means the Services and Products that McLeodUSA identifies in writing
as a System.

"Transaction Document," means a document or documents provided by McLeodUSA
before a business transaction under the Agreement occurs that confirms the
details of the transaction, and which will not be effective unless and until the
Parties agree in writing to its contents.

"User Identification," means a code or codes that enable authorization or access
to programs, data or equipment through Services.

"Yorktown Heights," means Prodigy's data center located in Yorktown Heights, New
York.

3.   Term.    This Agreement is in effect for thirty-six (36) months from the
--   -----
Effective Date. The Agreement will automatically renew for successive one (1)
year terms beginning July 1, 2004, and each July 1 thereafter, unless a Party
provides written notice of termination at least six (6) months prior to the end
of the then current term. However, if McLeodUSA is acquired by any of the
following entities or their affiliates or successors (AT&T, MCI WorldCom,
AOL/Time Warner, Earthlink, Sprint or Microsoft), Prodigy in its sole discretion
has the right to accelerate termination of this agreement upon ninety (90) days
prior written notice.

4.   Orders for Services or a Product.    Prodigy may order Services or a
--   ---------------------------------
Product in writing delivered by hand, mail or facsimile. The order is accepted
and becomes subject to this Agreement when McLeodUSA provides Prodigy with a
Transaction Document, which accepts expressly and precisely the terms of the
order. Prodigy shall indicate its acceptance of any additional terms in a
Transaction Document or attachment by signing the document and returning it to
McLeodUSA.

5.   Electronic Communications.    The Parties may communicate with the other
--   --------------------------
by electronic means for information purposes only, such as through electronic or
Prodigy

                                       2
<PAGE>

Mail. Any electronic communication must be followed by written confirmation or
be telecopied in order to be binding on either party. Documents, which include
handwritten signatures, may be transmitted by telecopier, and shall be deemed
binding without the need for original signatures, although original signature
copies are preferred.

6.   Prices.    By executing this Agreement, Prodigy commits to pay McLeodUSA
--   -------
minimum monthly revenue of four million five hundred thousand dollars ($4.5M) in
the following manner:  (a) a fixed, recurring one million dollars ($1M) network
access charge regardless of traffic or usage, and (b) a traffic or usage based
charge of three million five hundred thousand dollars ($3.5M).  The traffic or
usage based revenue will be calculated on market specific hourly rates and
minimum traffic or usage commitments per POP as provided for in Schedule 25.1 to
this Agreement.  Schedule 25.1 may be modified from time to time consistent with
this Agreement.  If new products or services are added, the prices will be
stated in the applicable Transaction Document.  Unless specifically agreed to in
writing, no additional charges shall be imposed or incurred for Services under
this Agreement.  McLeodUSA shall provide Services to Prodigy at prices no less
favorable than similar Services are sold to any other customer of McLeodUSA
under similar terms and conditions governed by the customer's credit worthiness,
the term of the Services, pricing structure, geographic coverage, perfomance
requirements, and related credits and minimum financial commitments (in
aggregate and by POP).  NAP fees previously charged by McLeodUSA under prior
agreements will be discontinued upon the Effective Date of this Agreement.

7.  Payment and Taxes.    (a) Prodigy shall pay:  (1) usage and recurring
--  ------------------
charges as provided for in the Agreement; and (2) all other charges when or
after they are incurred.  Amounts due are payable as specified in the invoice,
which invoice shall be consistent with the terms of this Agreement.

(b) Prodigy agrees to pay any tax on the Services provided except as provided
below. Prodigy is responsible for personal property taxes for each Product
purchased and each Program licensed to you from the date the Product or Program
is shipped or otherwise made available.  Prodigy shall be responsible for sales,
use, property, and other taxes on machines, software, or goods and services
provided by it.

(c) McLeodUSA shall be responsible for payment of sales, use, property, and
other taxes on machines, software, or goods and services used or furnished by
McLeodUSA for its own use in providing the Services to Prodigy.  All taxes
incurred in connection with the upgrade of the network to ATM switching, or any
other upgrade, whether mandatory or voluntary, shall be the sole responsibility
of McLeodUSA.

(d) Taxes, as used in this Agreement, shall not include any FCC charges or other
charges payable to any government organization other than a taxing authority,
all of which McLeodUSA shall pay.

(e) McLeodUSA shall make reasonable efforts to provide invoices on or before the
tenth day of the month following the monthly period being invoiced and Prodigy
agrees to pay invoices within thirty (30) days of the invoice date.  Prodigy
agrees to make payment by wire funds transfer.  If Prodigy fails to make
payments by the applicable invoice date, it agrees to pay a service charge equal
to the lesser of 1.5% per month or the maximum allowable rate under applicable
law on each unpaid amount.

                                       3
<PAGE>

8.  Patents and Copyrights.    (a) Claim. For purposes of this Section only, the
--  -----------------------        ------
term "Product" includes Materials alone or in combination with Products provided
as a System.  If a third party claims that a Product McLeodUSA provides to
Prodigy infringes that party's patent or copyright, McLeodUSA will defend
Prodigy against that claim.  McLeodUSA will pay all costs, damages, and
attorney's fees, provided that Prodigy:  (1) promptly notifies McLeodUSA in
writing of the claim; and (2) with its full cooperation, allows McLeodUSA to
control the defense of any claim and any related settlement negotiations.  At
Prodigy's option and at its cost, Prodigy may retain its own counsel to advise
it with regard to the cooperative efforts with McLeodUSA.  If a claim is made or
appears likely to be made, McLeodUSA will take reasonable steps, and Prodigy
agrees to permit McLeodUSA to do so, to enable Prodigy to continue to use the
Product, or to modify it, or replace it with one that is at least functionally
equivalent.  If McLeodUSA determines that none of these alternatives is
reasonably available, Prodigy agrees to return the Product to McLeodUSA upon
written request and McLeodUSA may terminate the affected Product at no further
charge to Prodigy, in which case McLeodUSA will refund to Prodigy the unused
prorata portion of any advance payments for the Product.

(b) PRODIGY AGREES THAT ITS RIGHTS, AS PROVIDED BY THIS SECTION REGARDING ANY
CLAIM OF INFRINGEMENT ARE LIMITED AND THE REMEDIES IN THIS SECTION WILL BE YOUR
SOLE AND EXCLUSIVE REMEDY FOR ANY SUCH CLAIM.

(c) Notice of Infringement. All notices of patent or copyright infringement
---------------------------
permitted or required by this Agreement will be in writing and will take effect
upon receipt.

(d) Claims for Which McLeodUSA is Not Responsible. McLeodUSA has no obligation
    ----------------------------------------------
regarding any claim to the extent it is based on any of the following:  (1)
Prodigy's modification of a Product, or a Program's use with equipment and
programs other than the Equipment and Programs with which the Program is
designed to operate; (2) the combination, operation, or use of a Product with
any product, data, or apparatus that McLeodUSA did not provide unless McLeodUSA
had written notice and acknowledged in writing receipt of notice that the
intended use of the Product was for a use with a product, data, or apparatus we
did not provide; or (3) infringement by a non-McLeodUSA Product alone, as
opposed to its combination with Products McLeodUSA provides as a System.

9.  Limitation of Liability.    (a) Circumstances may arise where, because of a
--  ------------------------
McLeodUSA default or other liability, Prodigy is entitled to recover damages.
Except for indemnification and failure to meet performance standards and service
level credits, in each such instance, regardless of the basis on which Prodigy
is entitled to claim damages, McLeodUSA is liable only for:  (1) payments
referred to in our patent and copyright section described above; (2) bodily
injury (including death), and damage to real property and tangible personal
property; and (3) the amount of any other actual loss or damage, in excess of
$100,000 or the charges (if recurring or usage, 12 months' charges apply) for
the Service or Product that is the subject of the claim.  This limit also
applies to any McLeodUSA subcontractors, agents and Program developers.  It is
the maximum for which McLeodUSA, its subcontractors, agents and program
developers are collectively responsible.

                                       4
<PAGE>

(b) Items for Which Neither Party is Liable. Under no circumstances are either
    ----------------------------------------
Party or its subcontractors, agents or Program developers liable for any of the
following:  (1) third-party claims against a Party for losses or damages (other
than those under (a)(1) and (a)(2) in this Section) except for willful acts or
acts of gross negligence; (2) loss of, or damage to, records or data except for
any actual loss or damage willfully and intentionally caused by a Party or
caused by gross negligence, subject to the limitation contained in (a)(3) of
this Section; or (3) economic consequential damages (including lost profits or
savings) or incidental damages, even if either Party is informed of their
possibility.

(3) EACH PARTY AGREES THAT ITS RIGHTS ARE LIMITED BY THIS SECTION, THAT THE
LIMITATIONS PROVIDED HEREIN ARE FAIR AND EQUITABLE, AND EACH PARTY HEREBY WAIVES
ANY RIGHT OR REMEDY IT MAY HAVE FOR THE RECOVERY OF ANY OTHER DAMAGES.

10.  Additional Rights.    Prodigy may have additional rights under certain laws
---  ------------------
(such as consumer laws) which do not allow the exclusion of implied warranties,
or the exclusion or limitation of certain damages.  If these laws apply,
McLeodUSA's exclusions or limitations may not apply to Prodigy.

11.  Geographic Scope.    All of your rights, all our obligations, and all
---  -----------------
licenses are valid only in the fifty (50) United States.

12.  Governing Law.    This Agreement shall be governed by and interpreted under
---  --------------
the laws of the state which is the domicile of the party who is an initial
defendant in any action or the party upon whom an initial demand for arbitration
is served.  Any action or arbitration proceeding shall be brought in the state
or federal courts located in that same state.

13.  Notices.    All notices or other communications shall be deemed to have
---  --------
been given when made in writing and either: (a) delivered in person; (b)
received within twenty-four (24) hours after delivery to an agent, such as an
overnight or similar delivery services; all delivery services prepaid; or (c)
received within 72 hours after deposited in the United Sates mail, postage
prepaid, and addressed as follows:

McLeodUSA                               Prodigy
---------                               -------

McLeodUSA Information                   Prodigy Communications,
Services, Inc.                          Limited Partnership
15 East 5th Street                      6500 River Place Boulevard
Suite 1800                              Building III
Tulsa, OK  74103                        Austin, TX  78730
ATTN:  Contract Administration          ATTN:  President

With copies to:
---------------
McLeodUSA Telecommunications            Prodigy's General Counsel
Services, Inc.                          Same address as above
Attn: Law Group
McLeodUSA Technology Park
P.O. Box 3177
Cedar Rapids, IA 52406-3177

                                       5
<PAGE>

Or at such other addresses as the Parties may from time to time in writing
designate.  If notice is provided by overnight mail, the address is 6400 C
                                     --------------                 ------
Street SW, Cedar Rapids, Iowa 52404.  Except where the context otherwise
-------------------------------------
indicates, all notices and documents shall be deemed to have been given on the
day received.

14.  Financial Covenants.    From the Effective Date and during the term of this
---  --------------------
Agreement, McLeodUSA covenants and agrees that it will:

(a)  Provide financial and other information consisting of:  (1) Annual
                                                                 ------
Financial Reports. Provide upon request of Prodigy a copy of McLeodUSA's 10-K
------------------
filed with the SEC. In addition, McLeodUSA shall provide immediate notice to
Prodigy in the event that it receives an qualified opinion concerning its
ability to continue as a going concern and/or the likelihood of any substantial
impairment of its assets. In the event that McLeodUSA ceases to be a public
company required to file a 10-K, then within ninety (90) days after the close of
each calendar year, a balance sheet as of the end of McLeodUSA's fiscal year, a
statement of operations and statement of cash flows.

(2) Quarterly Financial Statements. Provide upon request of Prodigy a copy of
    -------------------------------
McLeodUSA's latest 10-Q filed with the SEC.  In the event that McLeodUSA ceases
to be a public company required to file a 10-Q, then within ninety (90) days
after the close of each quarter, a balance sheet as of the end of the quarter, a
statement of operations and statement of cash flows.

(3) Payables.  Not later than forty-five (45) days after the close of each
    ---------
calendar quarter, beginning with the quarter commencing July 1, 2001, a total of
amounts which are due and payable and have not been paid by their contractual
due date, and a list of each creditor to which payments over $500,000 are due.

(4) Taxes.  Prompt payment without interest or penalty, all taxes, assessments
    -----
and similar imposts and charges of every kind and nature lawfully levied,
assessed or imposed upon McLeodUSA, except to the extent being contested in good
faith and furnish Prodigy evidence of such payment on a quarterly basis within
forty-five (45) days after the close of each calendar quarter.

(5) Liens and Litigation.  Notice, within ten (10) days of receipt of notice of
    ---------------------
any lien or lawsuit which is threatened or pending against McLeodUSA and which
involves a claim in excess of $1,000,000.

(6) Projections.  Within thirty (30) days after receipt of forecasts required by
    ------------
the Agreement for each applicable quarter, plans and projections for income,
expenses, capital receipt and expenditure, for the immediately succeeding
fifteen (15) month period.  Included with the statements to be provided
quarterly pursuant to this Section, McLeodUSA shall also provide evidence of
results as compared to past projections, which shall also be certified as true
by its chief executive or financial officer.

(7) Delisting.  Written notice of any delisting of McLeodUSA stock by the NASDAQ
    ----------
stock exchange within ten (10) days from notice of the delisting.

                                       6
<PAGE>

(8) Confidentiality.  Written notice where McLeodUSA used customer use patterns
    ----------------
in violation of this Agreement's confidentiality provisions to compete or to
assist others to compete against Prodigy.

(b) Maintain valid and effective insurance policies that cover McLeodUSA
properties and risks of the business in such types and amounts as are consistent
with customary practices and standards of companies engaged in businesses and
operations similar to Prodigy's and furnish not later than 45 days after the
close of each calendar quarter, beginning with the quarter commencing July 1,
2001, certificates evidencing such insurance.  After the receipt of such
certificate, Prodigy may request that McLeodUSA obtain additional coverage,
consistent with reasonable business practices which McLeodUSA shall obtain.

15.  Headings.    The headings contained herein are inserted for convenience or
---  ---------
reference only and are not intended to be part of or to affect the meaning or
interpretation of this Agreement.

16.  Mutual Responsibilities.    The Parties agree that: (a) neither party
---  ------------------------
grants the other the right to use its trademarks, trade names, or other
designation in any promotion or publication; (b) all information exchanged by
both parties is not confidential unless such information is conspicuously marked
as confidential and is managed as otherwise provided for in this Agreement; (c)
each Party grants the other only the licenses specified. No other licenses
(including licenses under patents) are granted; (d) each Party will promptly
notify the other if it becomes aware of any unsafe conditions or hazardous
materials to which the other's personnel would be exposed at any of its
facilities; (e) NEITHER PARTY WILL BRING A LEGAL ACTION OR REQUEST ALTERNATIVE
DISPUTE RESOLUTION MORE THAN TWO YEARS AFTER THE CAUSE OF ACTION AROSE UNLESS
SUCH CLAIM IS AS A RESULT OF A THIRD PARTY CLAIM, IN WHICH EVENT THE TWO YEAR
PROVISION SHALL NOT APPLY; (f) neither Party is responsible for failure to
fulfill its obligations (other than payment obligations) due to causes beyond
its reasonable control, including without limitation, acts of God, war, riots,
blockades, insurrections, labor disputes, lockouts, earthquakes, fires, storms,
lightning, power failures, floods, natural disasters, accidents, new or changed
governmental regulations or laws, or other similar events beyond the reasonable
control of the party relying on this provision of the Agreement ("Force
Majeure"); and (g) each Party will comply with all applicable laws regulations
or conventions including those related to data privacy, international
communications and exportation of technical or personal data. Each Party is
responsible for obtaining all necessary governmental regulatory or statutory
approvals for the offering of any services.

17.  McLeodUSA Responsibilities.    McLeodUSA will: (a) not assign, or otherwise
---  ---------------------------
transfer, this Agreement, or its rights or obligations under it, or delegate its
rights or Prodigy's obligations, other than to a McLeodUSA affiliate, without
Prodigy's prior written consent, which consent will not be unreasonably
withheld, provided, however, that McLeodUSA will be able, without Prodigy's
consent, to assign any rights and delegate any duties contained in this
Agreement to any entity into which McLeodUSA may be merged or consolidate or
which purchases all or substantially all of its assets; (b) obtain, install and
maintain suitable equipment as necessary to provide the

                                       7
<PAGE>

Services; (c) fulfill all regular activity and performance reporting and
analysis, including service disruption analysis, periodic audits, and attend and
participate actively in monthly status meetings which shall be held no less
frequently than monthly between the Parties; and (d) be responsible for data,
programs or other material that McLeodUSA provides for use with the Service.

18.  Prodigy Responsibilies.    Prodigy agrees: (a) not to assign, or otherwise
---  -----------------------
transfer, this Agreement or Prodigy's rights under it, or delegate Prodigy's
rights without prior written consent of McLeodUSA, which consent will not be
unreasonably withheld, provided however, that Prodigy will be able, without the
consent of McLeodUSA, to assign this Agreement or to assign any rights or
delegate any duties contained in this Agreement to an affiliate of Prodigy; (b)
to allow McLeodUSA to install mandatory engineering changes (such as those
required for safety) on Equipment; (c) that it is responsible for the results
obtained from the use of the Services and Products; (d) to provide McLeodUSA
with sufficient, and safe access to Prodigy facilities for McLeodUSA to fulfill
its obligations during reasonable hours and under such conditions as Prodigy may
reasonably impose; (e) to control and be responsible for issuance of User
Identifications and their distribution to End Users; (f) to be responsible for
data, programs, or other material that Prodigy provides for use with a Service;
(g) that McLeodUSA has no liability to those whom Prodigy authorizes to access a
service; (h) that McLeodUSA is not responsible for any data or text not
generated by McLeodUSA, including the content and accuracy, which is received,
routed or sent as a result of the Services McLeodUSA provides; and (i) that
McLeodUSA is free to enter into any agreements with third parties that are
similar or dissimilar to this Agreement without Prodigy's consent or approval.

19.  Warranty of Services.    (a) McLeodUSA warrants that it will provide
---  ---------------------
Services in a workmanlike manner, consistent with industry standard according to
its current Services description contained in the Agreement, any attachment or
Transaction Document, and in a manner so that the Services and the network shall
be compatible with Prodigy's equipment.

(b) OTHER THAN AS EXPRESSLY PROVIDED IN THE AGREEMENT, MCLEODUSA DISCLAIMS ALL
WARRANTIES, INCLUDING THE IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE, AND NON-INFRINGMENT.

20.  Items Not Covered by Warranty.    McLeodUSA does not warrant uninterrupted
---  ------------------------------
or error-free operation of a Service or Product. McLeodUSA will specifically
identify Services and Products that have a warranty, other than as described in
this and Section 19, and the terms of that warranty. Unless McLeodUSA specifies
otherwise in this Agreement it provides Materials, non-McLeodUSA Services and
non-McLeodUSA Products on an "AS IS" basis without any warranty from McLeodUSA.
Non-McLeodUSA manufacturers, suppliers, or publishers may provide their own
warranties.

21.  Equipment Provided by McLeodUSA.    Any Equipment installed on a Prodigy
---  --------------------------------
premises for purposes of providing services is and will remain a McLeodUSA asset
or that of any lessor, and will not become a fixture or realty.  Any Equipment

                                       8
<PAGE>

containing licensed internal code will identified to you.  No right, title, or
interest in or to the Equipment, or licensed internal code associated with it,
or any related planning information, is conveyed to Prodigy although the
Equipment is used to provide Services to you.

22.  Confidentiality.    (a) McLeodUSA agrees not to disclose Prodigy
---  ----------------
confidential information, including programs and data transmitted using the
Services and usage forecasts as described in this Agreement, nor shall McLeodUSA
disclose or use Prodigy customer private information, such as name, address,
credit card or other information which may be transmitted using the Services.
Geographic service usage patterns are also considered to be confidential and
shall not be used by McLeodUSA to directly compete with Prodigy or to assist
others in competing directly with Prodigy. McLeodUSA has no obligation of
confidentiality relating to Prodigy or its information which is not confidential
or which Prodigy does not conspicuously mark as confidential. McLeodUSA
acknowledges that all Prodigy customer information, and information about
Prodigy individual customers is confidential. Information that is not
confidential includes information which is: (1) either currently publicly
available or becomes publicly available in the future without a McLeodUSA breach
of any obligation or responsibility described in this Agreement; (2) rightfully
received by either Party from a third party, where the information was received
without any obligation of confidentiality associated with it; (3) already in a
the possession of McLeodUSA without an obligation of confidentiality; (4)
independently developed by McLeodUSA; (5) approved for disclosure by Prodigy; or
(6) treated by Prodigy as non-confidential.

(b) McLeodUSA has no liability for any disclosure of information that occurs as
the result of its delivery of Prodigy information, at Prodigy's direction and to
a recipient Prodigy designates, when the delivery is made in the normal course
of Services provisioning (for example, to an incorrect delivery address provided
by Prodigy to McLeodUSA).  McLeodUSA may disclose information to the extent
required by law, but will give Prodigy as much advance notice of such potential
disclosure as reasonably possible.

(c) McLeodUSA will handle Prodigy information marked confidential in a
confidential manner, and Prodigy will not permit McLeodUSA confidentially marked
information to be disclosed.  Prodigy is responsible for developing and
maintaining reasonable and customary procedures, which will notify Prodigy of
any material security breach that affects the Services.  Prodigy agrees that any
information regarding a McLeodUSA security system will be McLeodUSA confidential
information.  For the purposes of operation and maintenance, McLeodUSA may use,
copy, store, and distribute internally Prodigy information but only to the
extent necessary for operation and maintenance.  McLeodUSA shall have no such
rights with respect to Prodigy customer information, or with respect to
information about Prodigy customers.  McLeodUSA agrees not to reverse assemble
or reverse compile Prodigy information.  McLeodUSA will use reasonable
procedures, but McLeodUSA does not guarantee that these procedures will prevent
the loss, alteration of, or improper access to, Prodigy information.  Prodigy
agrees that access to Prodigy information will not prohibit or prevent McLeodUSA
from developing or marketing any service or product so long as McLeodUSA does
not violate the confidential provisions of this Agreement.  For transmissions
carried over interexchange

                                       9
<PAGE>

carriers' and local exchange carriers' facilities, McLeodUSA is not responsible
for transmission errors, or corruption or security of data.

23.  Services Description.    McLeodUSA will provide Services consisting of the
---  ---------------------
following components:  (a) dial access network as described in Section 23.1; and
(b) regional servers connectivity as described in Section 23.2.

23.1  Dial Access Network.  (a) McLeodUSA will provide dial access for data
----  --------------------
transport for Prodigy End Users (for purposes of this section "Service").
McLeodUSA will provide this Service to Prodigy in all locations in which, on the
Effective Date of this Agreement, such dial access service already exists.

(b) The Service will be provided to all current dial access locations listed on
Schedule 25.1 to this Agreement plus other locations as McLeodUSA builds,
acquires new facilities, or has dial access facilities presently.  McLeodUSA may
substitute a new POP for an existing POP upon thirty (30) days prior notice of
the change and with sixty (60) days simultaneous usage so long as McLeodUSA
provides porting of the traffic to the new site.  Prodigy may request new sites
for local dial access; but McLeodUSA will not be obligated to provide dial
access Service in any new dial access location with usage in any month of less
than five thousand (5,000) dial hours unless McLeodUSA reviews the location for
the new site and approves the creation of a new site at such location, in its
sole discretion.  Within ninety (90) days of execution of this Agreement,
McLeodUSA will evaluate expanding its dial access coverage for all Prodigy
customers and provide Prodigy with pricing for such expansion on a per city rate
basis.  McLeodUSA can modify the site coverage only with Prodigy's permission,
unless the modification is for a substitution of existing coverage, in which
case McLeodUSA does not need Prodigy's permission but any new access number
added must be coordinated with Prodigy so that Prodigy's customers can be given
adequate notice of the change.  Any new dial access sites added by McLeodUSA for
Services will be available to Prodigy, if Prodigy chooses to use them.  The
Parties agree to discuss within a commercially reasonable timeframe, and from
time to time whether they should eliminate any of the POPs identified in
Schedule 25.1 due to underutilization or to provide a reduction in cost to
either party.  If the Parties agree that those locations should be eliminated,
McLeodUSA agrees to arrange for porting of those dial access numbers to another
provider of Prodigy's choice when technically and economically feasible.

(c) The Service shall include the receipt of inbound data dial traffic from
Prodigy's End Users and the muting of such traffic to another End User, to a
regional server, to Prodigy's data center at Yorktown Heights, or to the
selected Internet NAPs.  McLeodUSA will not support initiating a call to another
End User's telephone.  McLeodUSA shall, in its sole discretion, decide the
number of dial ports it provides to service each site, as well as the method it
uses to provide Service to each site provided the grades and performance
standards of service as set forth in this Agreement are met.  Examples of
methods McLeodUSA may use to provide this Service include:  (1) a physical site
presence with modem ports; or (2) a virtual presence using call forwarding or a
foreign exchange.

(d) All new access equipment provided by McLeodUSA will have speed capacity with
respect to backbone access, and with respect to End User access, consistent with
the

                                       10
<PAGE>

service that can and will be provided from that site.  McLeodUSA shall be
responsible for:  (1) inbound communications facilities (such as hunt groups,
measured business lines or DID trunks); (2) modem hardware including ports and
chassis; and (3) network equipment and communications facilities to transport
traffic from the McLeodUSA dial site to other sites, to Prodigy's data center at
Yorktown Heights and any NAPs.

(e) McLeodUSA shall transport the dial data traffic to Prodigy via TCP/IP over
ATM.  McLeodUSA will not change the terms or conditions of a Service without
Prodigy's approval, which Prodigy agrees will not be unreasonably withheld.

23.2.  Regional Servers.  Prodigy may provide, maintain and manage regional
-----  -----------------
servers at sites determined by Prodigy, which are to be geographically dispersed
and co-located at McLeodUSA network hub sites ("Regional Servers").  Such
equipment is limited to that which may be installed in a standard 19" rack per
site.  Prodigy shall provide, maintain and manage diagnostic equipment,
connection equipment that Prodigy may use to connect to McLeodUSA and associated
analog phone lines which Prodigy may use to manage Prodigy's Regional Servers.
In addition, Prodigy shall provide the electric power cables and the equipment
connection cables for the equipment Prodigy provides, including those cables,
required to connect Prodigy's equipment to McLeodUSA network equipment.  Prodigy
also agrees to comply with all safety requirements at each site.  Each Regional
Server will be Ethernet connected to the McLeodUSA network.  Neither McLeodUSA
nor any other McLeodUSA customer shall use Prodigy's Regional Servers for any
purpose except to support Prodigy's End Users.  McLeodUSA shall provide Prodigy
with access to McLeodUSA sites for the purpose of maintaining, upgrading and
servicing these Regional Servers at no additional cost to Prodigy.  Prodigy is
responsible for separately procuring from McLeodUSA the upstream connection from
the Regional Server.  The upstream connection is defined as the network
facilities used to transport traffic from the Regional Server to locations other
than the source dial node (such as Yorktown Heights or the Internet).  Cost for
such services will be negotiated if Prodigy wishes to deploy Regional Servers.
The Regional Servers will not be included in the service level objectives, as
provided in Section 24.

23.3.  V.92 Capability.  McLeodUSA will use commercially reasonable efforts to
-----  ----------------
provide support for v.92 modems within 120 days of an acceptable software
release of this feature from Nortel or other modem equipment partner used by
McLeodUSA (defined as either acceptable to McLeodUSA or a release that has been
commercially deployed) for the current modem platform(s) deployed in the
McLeodUSA network.  Both parties understand that the above time frame may be
extended for hardware or software issues associated with v.92 that may delay
implementation.

24.  Performance
---  -----------

24.1  Performance Standards.  McLeodUSA will have performance standards
----  ----------------------
objectives for End User-services as follows:

(a) Individual POP `24-hours' Call Failure Rate. For each individual access
    --------------------------------------------
number given to any End User, the Average 24-hours Call Failure Rate during a
month shall not exceed ten percent (10%) for the immediately succeeding two (2)
consecutive months and the

                                       11
<PAGE>

parties determine that the reason such rate exceeded 10% was not due to
Scheduled Maintenance. This Call Failure Rate is based on a minimum sample size
of eight thousand (8,000) calls per access number. At least thirty percent (30%)
of the subscribers using a particular access number will have IP Insight client
loaded in their software.

(b) Individual POP `Evening Hours' (6pm - 12am) Call Failure Rate. For each
    --------------------------------------------------------------
individual access number given to any End User, the Average Evening Hours Call
Failure Rate during a month shall not exceed thirteen percent (13%) for the
immediately succeeding two (2) consecutive months. This Call Failure Rate is
based on a minimum sample size of two thousand (2,000) per access number.  At
least thirty percent (30%) of the Subscribers using a particular access number
have IP Insight client loaded in their software.

(c) Individual POP `24-hours' Latency.  For each POP, the monthly median round
    ----------------------------------
trip ping times shall not be greater than three hundred (300) milliseconds.  The
measurement is the computed median ping time based on the aggregate of Active
Tests within the McLeodUSA Network infrastructure for a month with a minimum
sample size of two thousand (2,000) per POP.  The POPs to be sampled will be
mutually agreed upon and variable, starting with the Inverse Benchmark POPs.

(d) Individual POP `Evening Hours' Latency.  For each POP, the Evening Hours
    ---------------------------------------
monthly median round trip ping times shall not be greater than three hundred
fifty (350) milliseconds. The measurement is the computed median ping time based
on the aggregate of all Active Tests within the McLeodUSA Network infrastructure
for a month with a minimum sample size of four hundred (400) per POP.

(e) Rules Governing Performance Standards.  Performance Standards are based on
    --------------------------------------
an access number by access number basis.  Performance Standards are determined
upon the accuracy of Prodigy's four-month rolling monthly access number
forecast.  To the extent that Prodigy's access number forecast is inaccurate by
more than ten percent (10%), the Performance Standards shall not apply.  Insight
Data for Performance Standards will be collected by Prodigy the first Monday on
or after the fifth (5th) calendar day of each month.  Prodigy will provide
McLeodUSA access to IP Insight metrics via means defined in the existing
agreement Prodigy has with Visual Networks.  McLeodUSA and Prodigy agree to
jointly meet with the company responsible for IP Insight testing within sixty
(60) days after execution of the definitive agreement.  If any benchmark or
other measurement device as specified in this Agreement is discontinued either
by the provider or by contract termination, the Parties shall mutually agree
upon a replacement metric or system.

24.1.1  Definitions.  For purposes of this Section the following definitions
------  ------------
apply:

(a) "24 hours," means the full 24 hours of local time for the Prodigy's End
User.

(b) "Active Test," means network latency measures (pings) provided by Visual
Networks, Inc. measured from the McLeodUSA NASs to an interface router at a
point in Prodigy's network data center in Yorktown Heights and the routers at
the active peering points in McLeodUSA's network.

(c) "Average," means averages for individual access numbers that are calculated
using all samples collected by the reporting tools for a specific access number
during that month.

(d) "Call Failure Rate," means a combination of the busy and ring-no-answer
categories provided by the IPInsight client and management reporting tools.

(e) "CSV File," means a common separated variable file.

(f) "Evening hours," means from 6pm to 12am local time for the Prodigy End User.

                                       12
<PAGE>

(g) "Inverse Benchmark," means a product of Visual Networks, Inc. that is a
monthly comparison of the performance of ISPs and wholesale access vendors.

(h) "IPInsight," means a product of Visual Networks, Inc., that is a part of
Prodigy's access kit.  IPInsight collects information about End User PC
configuration, connectivity and throughput, and forwards that information to
Prodigy. IP Insight collects information about call failures and latency that is
used in the Performance Standards.

(i) "Latency," means circuit latency measured by pings performed from McLeodUSA
Network Points to specified targets in the McLeodUSA network.  McLeodUSA and
Prodigy will mutually agree upon all targets.  The starting set will be based
upon the POPs used in the monthly Visual Networks Inverse Benchmark test, or at
significant peering points in the McLeodUSA backbone network.

(j) "NAS," means network access server.

(k) "NOC," means network operation center.

(l) "PETS," means the Prodigy Event Tracking System.

(m) "Scheduled Maintenance," means the time period during which all scheduled
maintenance shall occur and shall be between 2 am and 5 am local time (where the
NAS is located).  McLeodUSA will notify Prodigy's data NOC of regularly
scheduled outages which directly effect Prodigy Internet customers ability to
login (authenticate) to a POP or the ability to navigate `the Internet' not less
than five (5) days in advance unless extenuating circumstances arise which
require McLeodUSA to take the necessary and prudent steps to maintain the
integrity of the dial-access and transport network on which Prodigy traffic is
carried.

24.2  Performance Standards Credits.
----  ------------------------------

(a)  Service Level Agreement Credits for Individual POP `24-hours' Call Failure
     --------------------------------------------------------------------------
Rate:  (1) A minimum of eight thousand (8000) call records must be received for
-----
each access number; (2) The application of service level credits are tied to
Prodigy's four-month rolling monthly forecast accuracy by Dial Access Number. To
the extent that Prodigy exceeds the Dial Access Number forecast by more than ten
percent (10%), the service level credits shall not apply for that number; (3) A
maximum of ten percent (10%) 24-hour Call Failure Rate is considered allowable;
(4) Credits are assessed per access number for all calls in any access city and
are expressed as a percentage above of the 24-hour allowable Call Failure Rate;
(5) Performance credits for service may only be applied during the month that
the Performance credits are earned; (6) Prodigy must request Performance credits
within thirty (30) days of the end of the monthly measurement period.

                                       13
<PAGE>

                              Credit Rate Table I

           1) Minimum of eight thousand (8,000) calls for the month

            2) Ten percent (10%) or greater Total Call Failure Rate

           3) Credit Rate = % of Monthly Invoice For the Failed City

            4) # of access numbers (in sample range) X Credit Rate

    5) At least thirty percent (30%) of the Subscribers using a particular
        access number have IP Insight client loaded in their software.

<TABLE>
<CAPTION>
    # of Sample Ranges               Credit Rate
    ------------------               -----------
    <S>                              <C>
     8,000 to 43,999 -                    .11%
     44,000 to 79,999 -                   .33%
     80,000 to 115,999 -                  .55%
     116,000 to 151,999 -                 .77%
     152,000 to 187,999 -                 .99%
     188,000 to 223,999 -                1.11%
     224,000 to 259,999 -                1.33%
     260,000 + -                         1.55%
</TABLE>

(b) Service Level Agreement Credits for Individual POP `Evening Hours (6pm -
    ------------------------------------------------------------------------
12am)' Call Failure Rate.  (1) A minimum of two thousand (2000) call records
-------------------------
must be received for each access number; (2) The application of service level
credits are tied to Prodigy's four (4) month rolling monthly forecast accuracy
by Dial Access Number.  To the extent that Prodigy exceeds the forecast by more
than ten percent (10%), the service level credits shall not apply for that
number; (3) A maximum of thirteen percent (13%) Evening Hour Call Failure Rate
is considered allowable; (4) Credits are assessed per access number for all
calls in any access city and are expressed as a percentage above the allowable
Evening Hour Call Failure Rate; (5) Performance credits for service may only be
applied during the month that the Performance credits are earned; (6) Prodigy
must request Performance credits within thirty (30) days of the end of the
monthly measurement period.  Calls in any access city and are expressed as a
percentage above the allowable Evening Hour Call Failure Rate.

                                       14
<PAGE>

                              Credit Rate Table II

            1) Minimum of two thousand (2,000) calls for the month

         2) Thirteen percent (13%) or greater Total Call Failure Rate

           3) Credit Rate = % of Monthly Invoice For the Failed City

            4) # of access numbers (in sample range) X Credit Rate

    5) At least thirty percent (30%) of the Subscribers using a particular
        access number have IP Insight client loaded in their software.

<TABLE>
<CAPTION>
    # of Sample Ranges              Credit Rate
    ------------------              -----------
    <S>                              <C>
     2,000 to 10,999 -                  .11%
    11,000 to 19,999 -                  .33%
    20,000 to 28,999 -                  .55%
    29,000 to 37,999 -                  .77%
    38,000 to 46,999 -                  .99%
    47,000 to 55,999 -                 1.11%
    56,000 to 64,999 -                 1.33%
    65,000 + -                         1.55%
</TABLE>

(c) Additional Performance Standard notification and request responsibilities:
(1) Within seven (7) days of PETS confirmation of a McLeodUSA material
infrastructure problem affecting Prodigy, McLeodUSA will provide Prodigy in
writing, a relief date, outlining all dependencies involved (if any) for
providing relief.  (2) McLeodUSA agrees to provide Prodigy a monthly copy of
McLeodUSA's Visual Network Benchmark report and CSV File, (as permitted under
the terms of the McLeodUSA agreement with Visual Networks) and disclose to
Prodigy all access numbers used for the Visual Network Bench Mark test.  (3)
Prodigy will notify McLeodUSA, in a commercially reasonable time frame, of any
authentication, RADIUS or other BackOffice system failures that may compromise
the McLeodUSA authentication network.  (4) If any benchmark or other measurement
device as specified in this agreement is discontinued either by the provider or
by contract termination, the parties shall mutually agree upon a replacement
metric or system.  (5) If any benchmark or other measurement device as specified
in this agreement is discontinued either by the provider or by contract
termination, the parties shall mutually agree upon a replacement metric or
system  (6) In the event the McLeodUSA network performance values for; Call
Failure Rate (CFR) for 24 hour or Evening Hours exceed the allowable performance
levels for an immediately succeeding two consecutive months, Prodigy upon
request and at its election, is entitled to performance credits from McLeodUSA
in the amount equal to appropriate Credit Rate from Credit Rate Table I or
Credit Rate Table II, of the invoiced amount per access number for those access
numbers exceeding the stated performance standard.  All credits are applied
within two invoice

                                       15
<PAGE>

periods. (7) In the event that McLeodUSA's network performance, as measured
against monthly Inverse Benchmark data, is below the following reported industry
average(s) for the number of months indicated below in any of the following
categories Prodigy, at its election, will be entitled to credits from McLeodUSA
as follows:

<TABLE>
<CAPTION>

-----------------------------------------------------------------------------------------------------------
     Category                       Prodigy Does Not Exceed          # of Consecutive     Monthly Invoice
                                    10% of the Forecast for               Months            Credit For
                                         Failed Cities?                                     Each Month
-----------------------------------------------------------------------------------------------------------
<S>                                <C>                                   <C>                 <C>
24 Hour Call Failure Rate                     Yes                             2                  2%
-----------------------------------------------------------------------------------------------------------
Evening-Hour Call Failure Rate                Yes                             2                  2%
-----------------------------------------------------------------------------------------------------------
Modem Connect                                 N/A                             3                 .5%
-----------------------------------------------------------------------------------------------------------
Average Download Time                         N/A                             3                 .5%
-----------------------------------------------------------------------------------------------------------
Average Web Throughput                        N/A                             3                 .5%
-----------------------------------------------------------------------------------------------------------
Business-Hour Call Failure Rate               Yes                             2                 .5%
-----------------------------------------------------------------------------------------------------------
</TABLE>

Notwithstanding the above, the maximum total credit under this Section 24.2(c)
for any given month shall not exceed two percent (2%).  In the event a credit
applies, it applies for each consecutive month and each month thereafter until
McLeodUSA meets or surpasses the applicable industry average category for two
consecutive months.

24.3  McLeodUSA - Other Responsibilities.    McLeodUSA will:
----  -----------------------------------

(a) provide Prodigy with a number for Prodigy's operations group or customer
service group to contact McLeodUSA help desk support, which shall be available
twenty-four (24) hours a day, seven (7) days a week, and staffed adequately to
answer the phone for all Services inquiries within sixty (60) seconds;

(b) use Prodigy's PETS trouble ticketing system in McLeodUSA efforts to resolve
Services Inquiries;

(c) provide Prodigy with a monthly report detailing the status of network
upgrades and expansions within ten days of the end of the immediately preceding
month;

(d) maintain the components, programs, equipment and materials McLeodUSA
provides under this Agreement;

(e) provide Prodigy with read only terminal access to McLeodUSA network
management system so Prodigy can verify operational status of all network modems
and components;

(f) by November 30, 2001,  provide Prodigy:  (1) Enhanced Prodigy NOC to
McLeodUSA NOC communications by providing immediate detection alerts of the
following:  (i) Failure of backbone circuits, (ii) POP failure, (iii) Dial Node
Failure, and

                                       16
<PAGE>

(iv) Peering Point Failure; and (2) within thirty (30) days of completion of the
"real time" alert communication tools above, McLeodUSA will provide Prodigy a
linked tool that will communicate to Prodigy an accurate list of NPA/NXX's
affected by the major failures listed above;

(g) provide Prodigy statistical utilization metrics for McLeodUSA dial access
network that is directly associated with providing dial access to Prodigy users.
These metrics include:  (1) modem ports available to Prodigy End Users; (2)
modem ports utilized by Prodigy End Users; and (3) length of time each port is
utilized;

(h) provide Prodigy with Time Delay statistical data by September 1, 2001.

(i) provide Prodigy with a hard copy map of McLeod's POPs and supporting
infrastructure on a quarterly basis.

(j) participate in formal quarterly meetings, at mutually agreeable dates, times
and locations to discuss the "state of the business" (e.g., performance and
build out), submit proposed agenda items one (1) week prior to the meeting.

(k) provide Prodigy by October 30, 2001 exclusive dedicated dial access numbers
for all POPs listed on Schedule 25.1 or as the Schedule is amended from time to
time;

(l) within 7 days of PETS confirmation of a McLeodUSA material infrastructure
problem affecting Prodigy,  provide Prodigy in writing, a relief date, outlining
all dependencies involved (if any) for providing relief;

(m) provide Prodigy a monthly copy of their Visual Network Benchmark report and
CSV File, (as permitted under the terms of McLeodUSA's agreement with Visual
Networks) and disclose to Prodigy all access numbers used for the Visual Network
Bench Mark test.  If the information is not available under McLeodUSA's
agreement with Visual Networks, McLeodUSA agrees to negotiate with Visual
Networks to obtain access for Prodigy;

(n) make commercially reasonable efforts to notify Prodigy of unscheduled
outages in any portion of the dial network that directly affects Prodigy
Internet customer's ability to login (authenticate) to a POP or the ability to
navigate the Internet;

(o) continue to provide Prodigy a current escalation list, process document and
timing commitments for restoration of unscheduled outage situations on a timely
basis and depending on the assigned severity level of an outage, the appropriate
level of McLeodUSA operational management personnel will engage with the
appropriate level of Prodigy management on current impact and resolution of the
unplanned outage(s);

(p) make commercially reasonable efforts to repair unscheduled outages as soon
as possible to minimize the impact on the Prodigy Internet customers.  Based on
the escalation process (referenced above), McLeodUSA will keep Prodigy informed
as to the current status of the unscheduled outage at set intervals;

(q) notify Prodigy's data NOC of regularly scheduled outages which directly
effect Prodigy Internet customers ability to login (authenticate) to a POP or
the ability to navigate `the Internet' not less than five (5) days in advance.
All Scheduled Maintenance will be performed within the daily rolling time zone
maintenance window (between 2 am and 5 am local time) unless extenuating
circumstances arise which require McLeodUSA to take the necessary and prudent
steps to maintain the integrity of the dial-access and transport network on
which Prodigy traffic is carried;

(r) As a part of the escalation process and notification for Prodigy, McLeodUSA
will provide 24 x 7 access for two (2) Prodigy employees to the McLeodUSA Data
NOC. McLeodUSA will provide two (2) fully equipped computer workstations
complete with

                                       17
<PAGE>

access to the Internet, PETS, and voice communications capability and training
in McLeodUSA NOC procedures for four (4) employees per year free of charge.
McLeodUSA operations staff and Prodigy operations staff will jointly establish
policies, standards and interface agreements to guide the interaction of Prodigy
personnel with McLeodUSA NOC personnel. This interface arrangement will include
specific guidelines governing the support and response time Prodigy should
expect to receive from McLeodUSA NOC operations. Each Prodigy representative
shall be subject to strict confidentiality and shall not disclose any
information, data, conversations or observations related to any McLeodUSA
customers, practices, policies, procedures, network topology or ongoing
restoration efforts. Each Prodigy representative will execute any applicable
confidentiality agreement requested by McLeodUSA with respect to the obligation
of confidentiality; and

(s) McLeodUSA and Prodigy agree to disclose their respective Visual Network
Benchmark access number list two days prior to the start of the monthly test
period.

24.4 Prodigy - Other Responsibilities.    Prodigy will:  (a) notify McLeodUSA,
---- ---------------------------------
in a commercially reasonable time frame, of any authentication, RADIUS or other
BackOffice system failures that may compromise the McLeodUSA authentication
network; (b) participate in formal quarterly meetings, at mutually agreeable
dates, times and locations to discuss the "state of the business" (e.g.,
performance and build out), submit proposed agenda items one (1) week prior to
the meeting; and (c) be responsible for supporting its End Users directly
through its help desk. Prodigy's operations group or customer service group will
contact the McLeodUSA help desk in regard to any reported problems with the
Service being provided by McLeodUSA.

25.  Charges.
---  --------

25.1.  Monthly Usage Charges.
-----  ----------------------

(a) With respect to monthly recurring usage, Prodigy agrees to pay McLeodUSA
based on:  (1) the greater of the total minimum monthly charge ($3.5M or as it
is amended  from time to time), or (2) the total number of monthly connect hours
of your End Users using the Service times the applicable rate per hour per city
as identified on attached Schedule 25.1; and (3) a fixed monthly network access
fee of $1M.  Regardless of any other provision in this Agreement, the total
charges that Prodigy pays to McLeodUSA per month will not be less than $4.5M (or
as it is amended from time to time).  Prodigy may purchase Services from
McLeodUSA for cities not identified on Schedule 25.1 for those cities and at the
rates shown on Schedule 25.2 and such purchase(s) will be included in
determining whether Prodigy has satisfied its minimum commitment under this
Section.

(b) When a decision has been mutually agreed to in writing that a city (POP or
group of POPs) is to be eliminated or added to the list of POPs on Schedule 25.1
and Schedule 25.2 or any other POPs used by McLeodUSA as of the Effective Date,
the Parties agree that the minimum commitment as outlined in Schedule 25.1, and
the $4.5M monthly payment as stated in this Section will be modified by the
amount of the monthly minimum commitment times the then current hourly rate for
that city (POP or group of POPs).

                                       18
<PAGE>

(c) For purposes of determining connect hours, the sequence of a call is as
follows:  dial port goes off hook, modem synchronization, protocol management,
call routed, Prodigy authentication, session live while user performing tasks,
user initiates end of session or the session otherwise ends, eventually
resulting in modem off-line and session termination (carrier dropped).
McLeodUSA will aggregate the total time of all calls, rounded up by city to the
nearest hour.  The length of each individual call will be calculated from the
time the port goes off hook to session end (modem off-line), rounded up to the
nearest second.

(d) In the event that the connect hours for any city (or POP or group of POPs)
in any month is less than the minimum monthly hours traffic commitment as
defined in Schedule 25.1, or the connect hours are within five thousand (5,000)
hours greater than the minimum monthly hours traffic commitment, McLeodUSA shall
notify Prodigy within five (5) business days prior to the end of any month of
that fact.

(e) All pricing for dial access covers speeds up to v.92 capability.  All
pricing of higher speed Services is subject to negotiation and agreement between
the parties.

25.2.  Reduction in Charges.    McLeodUSA represents that it will throughout the
-----  ---------------------
term of this Agreement vigorously pursue reductions in the per city charges
identified on Schedule 25.1 as a result of anticipated cost savings by
McLeodUSA.  To the extent that McLeodUSA realizes incremental cost savings
(defined as those that may accrue as a result of McLeodUSA becoming a CLEC,
installation of new equipment, removal of PRIs, installation of IMT trunks,
etc.) during the term of this Agreement, McLeodUSA will extend fifty percent
(50%) of the cost savings to Prodigy in the form of reduced per city charges on
the beginning of the seventh month following the reduction in costs to
McLeodUSA.  McLeodUSA further agrees to provide Prodigy this costing information
every six months for planning purposes with the first report due on January 1,
2002 and then by specific POP as cost reductions are realized.  McLeodUSA may
reduce any per city rate at any time to remain competitive with the prices of
other network providers.  So long as Prodigy meets the minimum traffic
commitment of Section 25.1 or pays the minimum monthly charge, Prodigy shall be
free to use other network providers for any location that Prodigy provides its
service and/or in any city identified on Schedules 25.1 and 25.2 as may be
amended from time to time.

26.  Forecasts.    (a) Prodigy shall provide McLeodUSA with a rolling four month
     ----------
forecast by the fifth (5th) of each month on access numbers that McLeodUSA
provides complete RADIUS information including DNIS information where provided
to McLeodUSA.  The forecast will provide, to the extent it deviates from the
prior forecast:  (1) Hours of traffic expected for each Prodigy dial access
number; (2) Forecasted time of peak busy hour per day per access number; (3)
Distribution of traffic by hour of day across all sites; and (4) Average session
length across all sites.

(b) McLeodUSA shall use this information to perform capacity planning for the
services provided under this Agreement. Prodigy understands and agrees that
McLeodUSA will utilize the forecast information to increase or decrease the dial
access capacity in each city where Prodigy forecasts hourly usage.  Further,
Prodigy understands and agrees that Prodigy must maintain at least the minimum
hourly traffic level per city specified in Schedule 25.1.  If the actual usage
level in any city is below the minimum, Prodigy shall

                                       19
<PAGE>

be subject to the specified minimum charges per city as provided in Section 25.
The parties further acknowledge and agree that McLeodUSA may make network
related financial commitments based upon Prodigy's forecasts, e.g. purchasing
additional circuits. If the usage is not within ten percent (10%) of Prodigy's
forecast within two (2) months of McLeodUSA adding the additional capacity,
McLeodUSA retains the right to modify the city traffic minimum requirement. This
per city minimum is subject to negotiation and revision between the Parties.

27.  Changes and Default.
---  --------------------

27.1 Undesirable Conditions.  (a) If any of the following undesirable events
---- -----------------------
occurs for two consecutive months or four months out of a twelve-month period,
Prodigy may terminate this Agreement upon forty-five (45) days written notice
("Notice of Termination"):  (1) Overall 24-Hour Call Failure Rate of all access
numbers is greater than fifteen percent (15%); (2) Overall Evening Hour Call
Failure Rate of all access numbers is greater than twenty (20%); (3) Overall 24-
Hour Latency of all access numbers is greater than five hundred (500)
milliseconds; (4) Overall Evening Hour Latency of all access numbers is greater
than seven hundred (700) milliseconds.

(b) If Prodigy desires to terminate this Agreement because of any of the
foregoing undesirable conditions, it must give McLeodUSA a Notice of Termination
within thirty (30) days of receiving the monthly report that gives rise to your
right of termination.  If Prodigy does not exercise its right of termination
within such thirty (30) day period and in the next month the applicable
undesirable condition no longer exists, then Prodigy waives any right of
termination for the applicable time period and this Agreement shall remain in
full force and effect.

(c) Upon Notice of Termination, McLeodUSA shall provide reasonable transition
assistance to you, for a period of up to six months, and no termination
adjustment charge or service level credits shall apply, nor shall charges
specified in Section 25.1(a) apply after the effective date of termination.
Upon termination of the Agreement and after all outstanding amounts owed to
McLeodUSA are paid by Prodigy, McLeodUSA will have ninety (90) days in which to
pay Prodigy any and all credits owed to Prodigy.

27.2.  System Wide Failure.  If fifty (50%) of the POP sites are failing to
-----  --------------------
provide access or Services for forty-eight (48) consecutive hours, then Prodigy
has the right to enter the McLeodUSA premises to assist McLeodUSA in operating
its network assets and direction of its employees, as is necessary to cure such
failure. McLeodUSA shall reimburse Prodigy for any reasonable expense Prodigy
incurs in doing so. McLeodUSA will cooperate with Prodigy's efforts in restoring
service to the network. Prodigy shall also have the right to terminate in
accordance with the termination provisions of Section 27.1. Upon termination of
the Agreement and after all outstanding amounts owed to McLeodUSA are paid by
Prodigy, McLeodUSA will have ninety (90) days in which to pay Prodigy any and
all credits owed to Prodigy.

27.3.  Financial Related Defaults.  (a) Event of Default.  The occurrence of
-----  ---------------------------      -----------------
any of the following events shall constitute an Event of Default:  (1) The
failure of McLeodUSA to perform any of its obligations and covenants under
Section 14; (2) If

                                       20
<PAGE>

Prodigy, in good faith, after reviewing any document or report required to be
delivered under Section 14, believes that there has been a material and adverse
change in business operations and conditions of McLeodUSA, financial or
otherwise, which in Prodigy's reasonable opinion will have a materially adverse
effect upon the operations, business, property, assets, financial condition or
credit of us or Prodigy; (3) If McLeodUSA is acquired, merges with or sells all
of its assets to AT&T, MCI WorldCom, AOL/Time Warner, Earthlink, Sprint or
Microsoft, or any of the affiliates or successors of these entities; or (4) If
McLeodUSA violates any of the Agreement's confidentiality provisions where
McLeodUSA has used Prodigy's customer use patterns to compete or to assist
others to compete against Prodigy.

(b) Remedies.  Upon the occurrence of an Event of Default in this Section,
    ---------
Prodigy shall have the right to terminate this Agreement upon ninety (90) days
written notice.  Upon termination of the Agreement and after all outstanding
amounts owed to McLeodUSA are paid by Prodigy, McLeodUSA will have ninety (90)
days in which to pay Prodigy any and all credits owed to Prodigy.

27.4.  Default (other than for Sections 27.1, 27.2 or 27.3).  (a) In the event
-----  -----------------------------------------------------
that either Party materially defaults in the performance of any of its duties or
obligations under this Agreement (other than Prodigy's failure to make timely
payments due to McLeodUSA) and does not substantially cure such default within
sixty (60) days after being given written notice specifying the default, then
the party not in default may, by giving written notice to the defaulting party,
terminate this Agreement ("Termination for Cause").

(b) In the event Prodigy does not make any payment of the non-disputed charges
due to McLeodUSA by the invoice date, McLeodUSA may terminate this Agreement
upon forty-five (45) days written notice of such default, provided that
McLeodUSA does not receive payment in full for such overdue payment within the
45-day time period.  In the event that Prodigy does not make any other payment
due to McLeodUSA within thirty (30) days of the invoice date, and such failure
is not remedied within sixty (60) days after written notice of nonpayment ("Cure
Period") then McLeodUSA may terminate this Agreement upon the expiration of the
Cure Period.

(c) In the event that Prodigy is in default (for reasons other than failure to
make timely payments due to McLeodUSA) and McLeodUSA elects to terminate this
Agreement, Prodigy may request an extension of this Agreement of up to six (6)
months as a transition period, provided that McLeodUSA, in its discretion,
agrees to provide such an extension.

(d) In the event that Prodigy terminates this Agreement because McLeodUSA is in
material default, then McLeodUSA will provide reasonable transition assistance
to Prodigy, for a period of up to six (6) months.  Upon termination of the
Agreement and after all outstanding amounts owed to McLeodUSA are paid by
Prodigy, McLeodUSA will have ninety (90) days in which to pay Prodigy any and
all credits owed to Prodigy.

28.  Other Terms.    (a) Prodigy is not allowed to test or repair the McLeodUSA
---  ------------
dial network, except as provided in Section 27.2, and except to send Prodigy's
own sample pings similar to that described in Section 27.3.

                                       21
<PAGE>

(b) The Parties agree to seek to bids for the OC-N connections to Yorktown
Heights as soon as is commercially reasonable and at a price that is mutually
acceptable.  The Parties agree to equally share the cost of such OC-N
facilities.  Until such bid is accepted by the Parties, the terms of the May 3,
2000 letter agreement for such facilities will govern.

29.  Auditing Procedures    (a) McLeodUSA shall maintain true and accurate
---  -------------------
accounting records, in accordance with sound accounting practices, to support
the dial connect charges payable by Prodigy.  McLeodUSA shall, upon thirty (30)
days' prior written request, during normal business hours, but not more
frequently than once each calendar quarter, provide access to its records,
associated only with the provision of the Service for the immediately preceding
one-year period, to an independent accounting firm or Prodigy internal auditors
chosen and compensated by Prodigy for the purposes of auditing the accuracy of
the calculation of the dial connect charges.  The accounting firm or internal
auditors selected shall: be required to sign an agreement with protecting
confidential information, perform such audit on our premises, and such other
locations reasonably necessary to conduct a proper audit, comply with security
procedures, and be authorized by McLeodUSA to report only the results of such
audit and provide McLeodUSA with a copy of the report.

(b) In the event that the audit shows that Prodigy owes money to McLeodUSA,
McLeodUSA will invoice Prodigy for such amount within the next two monthly
billing cycles.

(c) In the event that the audit shows a credit due to Prodigy, McLeodUSA will
process such credit including the cost of the audit (but such costs shall not
exceed the credit), excluding travel and per diem charges, plus interest at the
prime rate on the entire amount until paid in full within the next two monthly
billing cycles, provided that McLeodUSA does not disagree with the audit report.
If McLeodUSA disagrees with the audit report, it may select an independent
accounting firm, compensated by it, to perform an audit on the same information
provided to the firm selected by Prodigy.  McLeodUSA shall provide Prodigy a
copy of the report.  In the even that the audit reports disagree on the credit
due to Prodigy, the Parties will resolve the dispute in accordance with Section
31.

30.  Preferred Provider.    (a) McLeodUSA shall be Prodigy's preferred provider
---  -------------------
of dial network access Services except for Prodigy's Agreements with SBC and
pre-existing agreements with other providers. Prodigy shall be free to make
agreements with third parties for Services subject to Prodigy's obligations to
comply with the terms of this Agreement, provided Prodigy shall not seek or
accept any bids for dial network access Services to replace McLeodUSA Services
in their totality (except for replacement of Services by services provided by
SBC). However, Prodigy is free to seek or accept bids for Services for those
cities (or POPs or groups of POPs) that have been eliminated as result of an
agreement between the Parties.

(b) Prodigy shall not offer other services that would result in a material
increase in costs to McLeodUSA, unless the Parties agree on the amount of
increased revenues which will bear a reasonable relationship to such increase in
our costs; provided that, if the Parties cannot agree on the amount of such
increased revenues, the McLeodUSA shall have no obligation to provide our
Services required for such other services.

                                       22
<PAGE>

31.  Alternative Dispute Resolution.    In the event of any dispute or
---  -------------------------------
controversy arising out of or relating to this Agreement, the Parties agree to
exercise their reasonable efforts to resolve the dispute as soon as possible.
The Parties shall without delay continue to perform their respective obligations
under this Agreement, which are not affected by the dispute. To invoke the
dispute resolution process set forth in this paragraph, the invoking party shall
give to the other party written notice of its decision to do so, including a
description of the issues subject to the dispute and a proposed resolution.

(b) Designated representatives of both Parties shall attempt to resolve the
dispute within five (5) working days after such notice.  If those designated
representatives cannot resolve the dispute, the Parties shall meet at Prodigy's
principal place of business or other location as jointly agreed by the Parties
and describe the dispute and their respective proposals for resolution to the
Chief Executive Officers of McLeodUSA and Prodigy, who shall act in good faith
to resolve the dispute.  If the dispute is not resolved within ten (10) calendar
days after such a meeting, the Parties may pursue any remedy available at law or
equity.

(c) Notwithstanding the above, the parties may seek injunctive relief or other
equitable remedies when irreparable injury will occur and no adequate remedy at
law exists.

32.  Publicity.    Each Party will (a) consult with the other party before
---  ----------
issuing any public statement with respect to this Agreement, and (b) give the
other Party a reasonable opportunity to review and comment upon any such
proposed public statement and receive written consent before it is released.

33.  Amendment.    No provision of this Agreement may be modified, waived or
---  ----------
discharged unless such waiver, modification or discharge is agreed to in writing
and signed by the Parties.

34.  Counterparts.    This Agreement may be executed in two or more
---  -------------
counterparts, each of which shall be deemed to be an original, but all such
counterparts shall together constitute one.

35.  Entire Agreement.    This Agreement, including any Schedules, Exhibits A, B
---  -----------------
and C, which is incorporated by reference, constitutes the entire agreement and
understanding between the parties.  Any amendments to this Agreement must be in
writing and executed by both parties.

                                       23
<PAGE>

IN WITNESS WHEREOF, the parties hereto have executed this Agreement on the date
indicated below.

PRODIGY COMMUNICATIONS                  MCLEODUSAUSA
LIMITED PARTNERSHIP                     INFORMATION SERVICES, INC.

By:  /s/ Paul Roth                      By:/s/ Roy A. Wilkens
     -------------                         ------------------

Name:  Paul Roth                        Name:  Roy A. Wilkens

Title: President & CEO                  Title: CEO Networks

Date:  August 1, 2001                   Date:  August 1, 2001

                                       24

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