<PAGE>

                                                                   Exhibit 10.18

               SECOND AMENDED AND RESTATED REGISTRATION AGREEMENT
               --------------------------------------------------

     THIS SECOND AMENDED AND RESTATED REGISTRATION AGREEMENT (this "Agreement")
                                                                    ---------
is made as of November 23, 1999, by and among CompleTel LLC (formerly known as
CableTel Europe LLC), a Delaware limited liability company (the "Company"),
                                                                 -------
Madison Dearborn Capital Partners II, L.P. ("MDCP"), DeGeorge Holdings Limited
                                             ----
Partnership ("DeGeorge Holdings"), Meritage Private Equity Fund, L.P.
              -----------------
("Meritage"), James C. Allen ("Allen"), Royce J. Holland ("Holland"), George T.
  --------                     -----                       -------
Laub ("Laub"), Reed E. Hundt ("Hundt"), Emile Karafiol ("Karafiol"), William S.
       ----                    -----                     --------
Kirsch ("Kirsch"), Northwestern University ("Northwestern"), Silver Cross
         ------                              ------------
Investors LLC ("SCI"), Dovey Company LLC ("Dovey LLC"), William H. Pearson
                ---                        ---------
("Pearson"), Haj LLC ("Pearson LLC #2"), Clevenger Company LLC ("Clevenger
  -------              --------------                            ---------
LLC"), David E. Lacey ("Lacey"), and the other holders of Registrable Securities
---                     -----
listed on the signature pages attached hereto. MDCP, DeGeorge Holdings,
Meritage, Allen, Holland, Laub, Hundt, Karafiol, Kirsch, Northwestern, and SCI
are referred to herein collectively as the "Investors" and individually as an
                                            ---------
"Investor." Capitalized terms used but not otherwise defined herein have the
 --------
meanings set forth in paragraph 8 hereof.

     As of May 18, 1998, the Company and MDCP, Lawrence F. DeGeorge
("DeGeorge"), James E. Dovey ("Dovey"), Pearson, and Richard N. Clevenger
  --------                     -----
("Clevenger") entered into a Registration Agreement (the "Prior Agreement"). As
  ---------                                               ---------------
of January 28, 1999, the parties (other than Meritage, Pearson LLC #2, Karafiol,
Kirsch, Northwestern, and SCI) entered into a First Amended and Restated
Registration Agreement (the "First Amended Agreement"), amending and restating
                             -----------------------
the Prior Agreement in its entirety. The parties hereto desire that, effective
as of the date hereof, the First Amended Agreement shall be amended and revised
in its entirety as set forth herein.

     NOW, THEREFORE, in consideration of the mutual promises made herein and
other good and valuable consideration, the receipt and sufficiency of which are
hereby acknowledged, the parties hereto, intending to be legally bound, agree as
follows:

     1.   Demand Registrations.
          --------------------

     (a)  Requests for Registration. At any time after the date hereof and prior
          -------------------------
to the Company's Initial Public Offering, the holders of a majority of the
Purchaser Registrable Securities then outstanding may request registration under
the Securities Act of all or any portion of their Registrable Securities on Form
S-1 or any similar long-form registration (a "Long-Form Registration"). After
                                              ----------------------
the Company's Initial Public Offering, (i) the holders of a majority of the MDCP
Registrable Securities then outstanding may request up to two Long-Form
Registrations, (ii) the holders of a majority of the DeGeorge Registrable
Securities then outstanding may request one Long- Form Registration, (iii) the
holders of at least 10% of the Purchaser Registrable Securities then outstanding
may request registration under the Securities Act of all or any portion of their
Registrable Securities on Form S-3 or any similar short-form registration
("Short-Form
  ----------
<PAGE>

Registrations") if available, and (iv) the holders of a majority of the Meritage
-------------
Registrable Securities then outstanding may request one Short-Form Registration,
if available; provided that the aggregate offering value of the Registrable
              --------
Securities requested to be registered in any registration under this paragraph
1(a) (any "Demand Registration") must equal at least $30 million if the
           -------------------
registration is the Company's Initial Public Offering, at least $15 million in
any other Long-Form Registration, and at least $5 million in any Short-Form
Registration; and provided further that the right of the holders of Meritage
              --------------------
Registrable Securities under clause (iv) above will terminate at such time as
Meritage and its affiliates cease to hold in the aggregate at least 50% of the
Meritage Registrable Securities held by Meritage on the date hereof.

     All requests for Demand Registrations shall be made by giving written
notice to the Company (the "Demand Notice"). Each Demand Notice shall specify
                            -------------
the approximate number of Registrable Securities requested to be registered and
the anticipated per share price range for such offering. Within ten days after
receipt of any Demand Notice, the Company shall give written notice of such
requested registration to all other holders of Registrable Securities and,
subject to the provisions of paragraph 1(d) below, shall include in such
registration all Registrable Securities with respect to which the Company has
received written requests for inclusion therein within 15 days after the receipt
of the Company's notice.

     (b) Expenses; Withdrawal. The Company shall pay all Registration Expenses
         --------------------
of all holders of Registrable Securities in all Demand Registrations. A
registration shall not count as one of the permitted Long-Form Registrations
(or, in the case of a Short-Form Registration requested by the holders of
Meritage Registrable Securities, as the one permitted Short-Form Registration
under Section 1(a)(iv)) until both (i) it has become effective and (ii) the
      ----------------
holders of Registrable Securities initially requesting such registration are
able to register and sell at least 90% of the Registrable Securities requested
to be included in such registration; provided that the Company shall in any
                                     --------
event pay all Registration Expenses in connection with any registration
initiated as a Demand Registration whether or not it has become effective and
whether or not such registration has counted as one of the permitted Long-Form
Registrations (or, if applicable, as the one permitted Short-Form Registration
under Section 1(a)(iv)). All Long-Form Registrations shall be underwritten
      ----------------
registrations unless otherwise requested by the holders of a majority of the
Registrable Securities included in the applicable Long-Form Registration.

     (c) Short-Form Registrations. Demand Registrations shall be Short-Form
         ------------------------
Registrations whenever the Company is permitted to use any applicable short
form. After the Company has become subject to the reporting requirements of the
Securities Exchange Act, the Company shall use its best efforts to make
Short-Form Registrations on Form S-3 (or any successor form) available for the
sale of Registrable Securities.

     (d) Priority on Demand Registrations. The Company shall not include in any
         --------------------------------
Demand Registration any securities which are not Registrable Securities without
the prior written consent of the holders of a majority of the Registrable
Securities included in such registration. If a Demand Registration is an
underwritten offering and the managing underwriters advise the Company

                                      -2-
<PAGE>

in writing that in their opinion the number of Registrable Securities and, if
permitted hereunder, other securities requested to be included in such offering
exceeds the number of Registrable Securities and other securities, if any, which
can be sold in an orderly manner in such offering within a price range
acceptable to the holders of a majority of the Registrable Securities initially
requesting registration, the Company shall include in such registration the
number which can be so sold in the following order of priorities: (i) first, the
Purchaser Registrable Securities requested to be included in such registration,
pro rata among the holders of such Purchaser Registrable Securities on the basis
of the number of shares owned by each such holder, (ii) second, the other
Registrable Securities requested to be included in such registration, pro rata
among the holders of such Registrable Securities on the basis of the number of
shares owned by each such holder, and (ii) third, other securities requested to
be included in such registration.

     (e) Restrictions on Long-Form Registrations. The Company shall not be
         ---------------------------------------
obligated to effect any Demand Registration which is a Long-Form Registration
within 180 days after the effective date of a previous Demand Registration
which was a Long-Form Registration or a previous registration in which the
holders of Registrable Securities were given piggyback rights pursuant to
paragraph 2 and in which such holders were able to register and sell at least
90% of the number of Registrable Securities requested to be included therein.
The Company may preempt any request for a Demand Registration in order to effect
an underwritten primary registration on behalf of the Company, provided that (i)
                                                               --------
such preempting underwritten primary registration must become effective within
90 days after the date such preempted Demand Registration is requested, (ii) the
holders of Registrable Securities initially requesting the preempted Demand
Registration must have piggyback rights pursuant to paragraph 2 with respect to
the preempting primary registration and must be able to register and sell
pursuant to such piggyback rights in such primary registration at least 90% of
the Registrable Securities initially requested to be included in the preempted
Demand Registration, (iii) the Company shall pay all Registration Expenses in
connection with any such preempting primary registration, and (iv) the preempted
Demand Registration shall not count as one of the permitted Demand Registrations
hereunder. The Company may preempt a Demand Registration hereunder only once in
any 12-month period. The Company may postpone for up to 180 days the filing or
the effectiveness of a registration statement for a Demand Registration if the
Company's board of directors determines in its reasonable good faith judgment
that such Demand Registration would reasonably be expected to have a material
adverse effect on any proposal or plan by the Company or any of its direct or
indirect subsidiaries to engage in any acquisition of assets (other than in the
ordinary course of business) or any merger, consolidation, tender offer,
reorganization or similar transaction; provided that in such event, the holders
                                       --------
of Registrable Securities initially requesting such Demand Registration shall be
entitled to withdraw such request and, if such request is withdrawn, such Demand
Registration shall not count as one of the permitted Demand Registrations
hereunder and the Company shall pay all Registration Expenses in connection with
such withdrawn registration. The Company may delay a Demand Registration
hereunder only once in any twelve-month period.

                                      -3-
<PAGE>

     (f) Selection of Underwriters. Subject to the approval rights granted to
         -------------------------
the holders of Purchaser Registrable Securities under the Equity Purchase
Agreement, the Board shall select the investment banker(s) and manager(s) to
administer the offering.

     (g) Other Registration Rights. Except as provided in this Agreement, the
         -------------------------
Company shall not grant to any Persons the right to request the Company to
register any equity securities of the Company, or any securities convertible or
exchangeable into or exercisable for such securities, without the prior written
consent of the holders of a majority of the Purchaser Registrable Securities
(or, if none, the Registrable Securities) then outstanding; provided that the
                                                            --------
Company may grant rights to other Persons to participate in Piggyback
Registrations so long as such rights are subordinate to the rights of the
holders of Registrable Securities with respect to such Piggyback Registrations;
and provided further that the Company may grant rights to other Persons to
--------------------
request registrations so long as the holders of Registrable Securities are
entitled to participate in any such registrations with such Persons pro rata on
the basis of the number of shares owned by each such holder.

     2.  Piggyback Registrations.
         -----------------------

     (a) Right to Piggyback. Whenever the Company proposes to register any of
         ------------------
its securities under the Securities Act (other than pursuant to a Demand
Registration) and the registration form to be used may be used for the
registration of Registrable Securities (a "Piggyback Registration"), the Company
                                           ----------------------
shall give prompt written notice (in any event within three business days after
its receipt of notice of any exercise of demand registration rights other than
under this Agreement) to all holders of Registrable Securities of its intention
to effect such a registration and shall, subject to the provisions of paragraph
2(c) below, include in such registration all Registrable Securities with respect
to which the Company has received written requests for inclusion therein within
20 days after the receipt of the Company's notice.

     (b) Piggyback Expenses. The Registration Expenses of the holders of
         ------------------
Registrable  Securities shall be paid by the Company in all Piggyback
Registrations.

     (c) Priority on Primary Registrations. If a Piggyback Registration is an
         ---------------------------------
underwritten primary registration on behalf of the Company, and the managing
underwriters advise the Company in writing that in their opinion the number of
securities requested to be included in such registration exceeds the number
which can be sold in an orderly manner in such offering within a price range
acceptable to the Company, the Company shall include in such registration (i)
first, the securities the Company proposes to sell, (ii) second, the Purchaser
Registrable Securities requested to be included in such registration, pro rata
among the holders of such Purchaser Registrable Securities on the basis of the
number of shares owned by each such holder, (iii) third, the other Registrable
Securities requested to be included in such registration, pro rata among the
holders of such Registrable Securities on the basis of the number of shares
owned by each such holder, and (iv) fourth, other securities requested to be
included in such registration.

                                      -4-
<PAGE>

     (d) Priority on Secondary Registrations. If a Piggyback Registration is an
         -----------------------------------
underwritten secondary registration on behalf of holders of the Company's
securities, and the managing underwriters advise the Company in writing that in
their opinion the number of securities requested to be included in such
registration exceeds the number which can be sold in an orderly manner in such
offering within a price range acceptable to the holders initially requesting
such registration, the Company shall include in such registration (i) first, the
securities requested to be included therein by the holders requesting such
registration and the Registrable Securities requested to be included in such
registration, pro rata among the holders of any such securities on the basis of
the number of securities so requested to be included therein owned by each such
holder, and (ii) second, other securities requested to be included in such
registration.

     (e) Selection of Underwriters. If any Piggyback Registration is an
         -------------------------
underwritten offering, subject to the approval rights granted to the holders of
Purchaser Registrable Securities under the Equity Purchase Agreement, the Board
shall select the investment banker(s) and manager(s) to administer the offering.

     (f) Other Registrations. If the Company has previously filed a registration
         -------------------
statement with respect to Registrable Securities pursuant to paragraph 1 or
pursuant to this paragraph 2, and if such previous registration has not been
withdrawn or abandoned, the Company shall not file or cause to be effected any
other registration of any of its equity securities or securities convertible or
exchangeable into or exercisable for its equity securities under the Securities
Act (except on Form S-8 or any successor form), whether on its own behalf or at
the request of any holder or holders of such securities, until a period of at
least 180 days has elapsed from the effective date of such previous
registration.

     3.  Holdback Agreements.
         -------------------

     (a) Holders of Registrable Securities. Each holder of Registrable
         ---------------------------------
Securities shall not effect any public sale or distribution (including sales
pursuant to Rule 144) of equity securities of the Company, or any securities
convertible into or exchangeable or exercisable for such securities, during the
seven days prior to and the 180-day period beginning on the effective date of
any underwritten Demand Registration or any underwritten Piggyback Registration
in which Registrable Securities are included (in each case, except as part of
such underwritten registration), unless in each case the underwriters managing
the registered public offering otherwise agree.

     (b) The Company. The Company (i) shall not effect any public sale or
         -----------
distribution of its equity securities, or any securities convertible into or
exchangeable or exercisable for such securities, during the seven days prior to
and during the 180-day period beginning on the effective date of any
underwritten Demand Registration or any underwritten Piggyback Registration
(except as part of such underwritten registration or pursuant to registrations
on Form S-8 or any successor form), unless the underwriters managing the
registered public offering otherwise agree, and (ii) shall cause each holder of
its Common Stock, or any securities convertible into or exchangeable or
exercisable for Common Stock, purchased from the Company at any time after the
date of

                                      -5-
<PAGE>

this Agreement (other than in a registered public offering or pursuant to Rule
144) to agree not to effect any public sale or distribution (including sales
pursuant to Rule 144) of any such securities during such period (except as part
of such underwritten registration, if otherwise permitted), unless the
underwriters managing the registered public offering otherwise agree.

     4. Registration Procedures. Whenever the holders of Registrable Securities
        -----------------------
have requested that any Registrable Securities be registered pursuant to this
Agreement, the Company shall use its best efforts to effect the registration and
the sale of such Registrable Securities in accordance with the intended method
of disposition thereof, and pursuant thereto the Company shall as expeditiously
as possible:

     (a) prepare and file with the Securities and Exchange Commission a
registration statement with respect to such Registrable Securities and use its
best efforts to cause such registration statement to become effective (provided
that before filing a registration statement or prospectus or any amendments or
supplements thereto, the Company shall furnish to the counsel selected by the
holders of a majority of the Registrable Securities covered by such registration
statement copies of all such documents proposed to be filed, which documents
shall be subject to the review and comment of such counsel);

     (b) notify each holder of Registrable Securities of the effectiveness of
each registration statement filed hereunder and prepare and file with the
Securities and Exchange 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 for a period of not less
than 180 days and comply with the provisions of the Securities Act with respect
to the disposition of all securities covered by such registration statement
during such period in accordance with the intended methods of disposition by the
sellers thereof set forth in such registration statement;

     (c) furnish to each seller of Registrable Securities such number of copies
of such registration statement, each amendment and supplement thereto, the
prospectus included in such registration statement (including each preliminary
prospectus) and such other documents as such seller may reasonably request in
order to facilitate the disposition of the Registrable Securities owned by such
seller;

     (d) use its best efforts to register or qualify such Registrable Securities
under such other securities or blue sky laws of such jurisdictions as any seller
reasonably requests and do any and all other acts and things which may be
reasonably necessary or advisable to enable such seller to consummate the
disposition in such jurisdictions of the Registrable Securities owned by such
seller (provided that the Company shall not be required to (i) qualify generally
to do business in any jurisdiction where it would not otherwise be required to
qualify but for this subparagraph, (ii) subject itself to taxation in any such
jurisdiction or (iii) consent to general service of process in any such
jurisdiction);

                                      -6-
<PAGE>

     (e) notify each seller of such Registrable Securities, at any time when a
prospectus relating thereto is required to be delivered under the Securities
Act, of the happening of any event as a result of which the prospectus included
in such registration statement contains an untrue statement of a material fact
or omits any fact necessary to make the statements therein not misleading, and,
at the request of any such seller, the Company shall prepare a supplement or
amendment to such prospectus so that, as thereafter delivered to the purchasers
of such Registrable Securities, such prospectus shall not contain an untrue
statement of a material fact or omit to state any fact necessary to make the
statements therein not misleading;

     (f) cause all such Registrable Securities to be listed on each securities
exchange on which similar securities issued by the Company are then listed and,
if not so listed, to be listed on the Nasdaq and, if listed on the Nasdaq, use
its best efforts to secure designation of all such Registrable Securities
covered by such registration statement as a Nasdaq "national market system
security" within the meaning of Rule 11Aa2-1 of the Securities and Exchange
Commission or, failing that, to secure Nasdaq authorization for such Registrable
Securities and, without limiting the generality of the foregoing, to arrange for
at least two market makers to register as such with respect to such Registrable
Securities with the National Association of Securities Dealers (the "NASD");
                                                                     ----

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

     (h) enter into such customary agreements (including underwriting agreements
in customary form) and take all such other actions as the holders of a majority
of the Registrable Securities being sold or the underwriters, if any, reasonably
request in order to expedite or facilitate the disposition of such Registrable
Securities (including effecting a stock split, a combination of shares, or other
recapitalization);

     (i) make available for inspection by any seller of Registrable Securities,
any underwriter participating in any disposition pursuant to such registration
statement and any attorney, accountant or other agent retained by any such
seller or underwriter, all financial and other records, pertinent corporate
documents and properties of the Company, and cause the Company's officers,
directors, employees and independent accountants to supply all information
reasonably requested by any such seller, underwriter, attorney, accountant or
agent in connection with such registration statement;

     (j) otherwise use its best efforts to comply with all applicable rules and
regulations of the Securities and Exchange Commission, and make available to its
security holders, as soon as reasonably practicable, an earnings statement
covering the period of at least twelve months beginning with the first day of
the Company's first full calendar quarter after the effective date of the
registration statement, which earnings statement shall satisfy the provisions of
Section 11(a) of the Securities Act and Rule 158 thereunder;

                                      -7-
<PAGE>

     (k) permit any holder of Registrable Securities which holder, in its sole
and exclusive judgment, might be deemed to be an underwriter or a controlling
person of the Company, to participate in the preparation of such registration or
comparable statement and to require the insertion therein of material, furnished
to the Company in writing, which in the reasonable judgment of such holder and
its counsel should be included;

     (l) in the event of the issuance of any stop order suspending the
effectiveness of a registration statement, or of any order suspending or
preventing the use of any related prospectus or suspending the qualification of
any Common Stock included in such registration statement for sale in any
jurisdiction, the Company shall use its best efforts promptly to obtain the
withdrawal of such order;

     (m) obtain a cold comfort letter from the Company's independent public
accountants in customary form and covering the matters customarily covered by
cold comfort letters as the holders of a majority of the Registrable Securities
being sold reasonably request; and

     (n) use its best efforts to cause such Registrable Securities covered by
such registration statement to be registered with or approved by such other
governmental agencies or authorities as may be necessary to enable the sellers
thereof to consummate the disposition of the Registrable Securities.

     5.  Registration Expenses.
         ---------------------

     (a) Expenses. All expenses incident to the Company's performance of or
         --------
compliance with this Agreement, including without limitation all registration
and filing fees, fees and expenses of compliance with securities or blue sky
laws, printing expenses, messenger and delivery expenses, fees and disbursements
of custodians, and fees and disbursements of counsel for the Company and all
independent certified public accountants, underwriters (excluding discounts and
commissions) and other Persons retained by the Company (all such expenses being
herein called "Registration Expenses"), shall be borne as provided in this
               ---------------------
Agreement, except that the Company shall, in any event, pay its internal
expenses (including, without limitation, all salaries and expenses of its
officers and employees performing legal or accounting duties), the expense of
any annual audit or quarterly review, the expense of any liability insurance and
the expenses and fees for listing the securities to be registered on each
securities exchange on which similar securities issued by the Company are then
listed or on the Nasdaq.

     (b) Reimbursement of Counsel. In connection with each Demand Registration
         ------------------------
and each Piggyback Registration, the Company shall reimburse the holders of
Registrable Securities included in such registration (i) for the reasonable fees
and disbursements (not to exceed $20,000 for any one registration) of one
counsel chosen by the holders of a majority of the Purchaser Registrable
Securities (or, if none, Registrable Securities) included in such registration
and (ii) for the reasonable fees and disbursements (not to exceed $5,000 per
additional counsel for any one registration) of each additional counsel retained
by any holder of Registrable Securities solely for

                                      -8-
<PAGE>

the purpose of rendering a legal opinion to underwriters on behalf of such
holder in connection with any underwritten Demand Registration or Piggyback
Registration.

     (c) Payment of Certain Expenses by Holders of Registrable Securities.
         ----------------------------------------------------------------
Underwriting discounts and commissions and transfer taxes relating to the
Registrable Securities included in any registration hereunder, and all fees and
expenses of counsel for any holder of Registrable Securities (other than fees
and expenses to be reimbursed by the Company as set forth in paragraph (b)
above) shall be borne and paid by the holders of such Registrable Securities.

     6.  Indemnification.
         ---------------

     (a) The Company agrees to indemnify, to the extent permitted by law, each
holder of Registrable Securities, its officers and directors and each Person
that controls such holder (within the meaning of the Securities Act) against all
losses, claims, damages, liabilities and expenses caused by any untrue or
alleged untrue statement of material fact contained in any registration
statement, prospectus or preliminary prospectus or any amendment thereof or
supplement thereto or any omission or alleged omission of a material fact
required to be stated therein or necessary to make the statements therein not
misleading, except insofar as the same are caused by or contained in any
information furnished in writing to the Company by such holder expressly for use
therein or by such holder's failure to deliver a copy of the registration
statement or prospectus or any amendments or supplements thereto after the
Company has furnished such holder with a sufficient number of copies of the
same. In connection with an underwritten offering, the Company shall indemnify
such underwriters, their officers and directors and each Person who controls
such underwriters (within the meaning of the Securities Act) to the same extent
as provided above with respect to the indemnification of the holders of
Registrable Securities.

     (b) In connection with any registration statement in which a holder of
Registrable Securities is participating, each such holder shall furnish to the
Company in writing such information and affidavits as the Company reasonably
requests for use in connection with any such registration statement or
prospectus and, to the extent permitted by law, shall indemnify the Company, its
directors and officers and each Person who controls the Company (within the
meaning of the Securities Act) against any losses, claims, damages, liabilities
and expenses resulting from any untrue or alleged untrue statement of material
fact contained in the registration statement, prospectus or preliminary
prospectus or any amendment thereof or supplement thereto or any omission or
alleged omission of a material fact required to be stated therein or necessary
to make the statements therein not misleading, but only to the extent that such
untrue statement or omission is contained in any information or affidavit so
furnished in writing by such holder; provided that the obligation to indemnify
shall be individual, not joint and several, for each holder and shall be limited
to the net amount of proceeds received by such holder from the sale of
Registrable Securities pursuant to such registration statement.

     (c) Any Person entitled to indemnification hereunder shall (i) give prompt
written notice to the indemnifying party of any claim with respect to which it
seeks indemnification

                                      -9-
<PAGE>

(provided that the failure to give prompt notice shall not impair any Person's
right to indemnification hereunder to the extent such failure has not prejudiced
the indemnifying party) and (ii) unless in such indemnified party's reasonable
judgment a conflict of interest between such indemnified and indemnifying
parties may exist with respect to such claim, permit such indemnifying party to
assume the defense of such claim with counsel reasonably satisfactory to the
indemnified party. If such defense is assumed, the indemnifying party shall not
be subject to any liability for any settlement made by the indemnified party
without its consent (but such consent shall not be unreasonably withheld). An
indemnifying party who is not entitled to, or elects not to, assume the defense
of a claim shall not be obligated to pay the fees and expenses of more than one
counsel for all parties indemnified by such indemnifying party with respect to
such claim, unless in the reasonable judgment of any indemnified party a
conflict of interest may exist between such indemnified party and any other of
such indemnified parties with respect to such claim.

     (d) The indemnification provided for under this Agreement shall remain in
full force and effect regardless of any investigation made by or on behalf of
the indemnified party or any officer, director or controlling Person of such
indemnified party and shall survive the transfer of securities. The Company also
agrees to make such provisions, as are reasonably requested by any indemnified
party, for contribution to such party in the event the Company's indemnification
is unavailable for any reason such that such provisions provide the same
obligations and benefits to the indemnified party as those which would have been
applicable had the indemnification provisions in paragraphs 6(a) and (b) been
available taking into account all of the limitations set forth in paragraphs
6(a) and (b).

     7. Participation in Underwritten Registrations. No Person may participate
        -------------------------------------------
in any registration hereunder which is underwritten unless such Person (i)
agrees to sell such Person's securities on the basis provided in any
underwriting arrangements approved by the Person or Persons entitled hereunder
to approve such arrangements and (ii) completes and executes all questionnaires,
powers of attorney, indemnities, underwriting agreements and other documents
required under the terms of such underwriting arrangements; provided that no
holder of Registrable Securities included in any underwritten registration shall
be required to make any representations or warranties to the Company or the
underwriters (other than representations and warranties regarding such holder
and such holder's intended method of distribution) or to undertake any
indemnification obligations to the Company with respect thereto, except as
otherwise provided in paragraph 6(b) hereof, or to the underwriters with respect
thereto, except to the extent of the indemnification being given to the Company
and its controlling persons in paragraph 6(a) hereof.

     8.  Definitions.
         -----------

     "Agreement" has the meaning set forth with respect thereto in the preamble.
      ---------

     "Allen" has the meaning set forth with respect thereto in the preamble.
      -----

                                     -10-
<PAGE>

     "Board" means the board of managers of the Company or, if the Company is
      -----
hereafter converted into a corporation or other entity form, the board of
directors or comparable governing body of the Company.

     "Clevenger" has the meaning set forth with respect thereto in the preamble.
      ---------

     "Clevenger LLC" has the meaning set forth with respect thereto in the
      -------------
preamble.

     "Common Stock" means the Common Units and, in the event the Company has
      ------------
hereafter converted into a corporation or other entity form, the common stock or
other comparable common equity securities of the Company.

     "Common Units" means the Common Units of the Company, having the rights and
      ------------
preferences set forth with respect thereto in the LLC Agreement.

     "Company" has the meaning set forth with respect thereto in the preamble.
      -------

     "DeGeorge" has the meaning set forth with respect thereto in the preamble.
      --------

     "DeGeorge Holdings" has the meaning set forth with respect thereto in the
      -----------------
preamble.

     "DeGeorge Registrable Securities" means Registrable Securities derived from
      -------------------------------
or relating to the Preferred Units issued to DeGeorge under the Equity Purchase
Agreement.

     "Demand Notice" has the meaning set forth with respect thereto in Section
      -------------
1(a).

     "Demand Registration" has the meaning set forth with respect thereto in
      -------------------
Section 1(a).

     "Dovey" has the meaning set forth with respect thereto in the preamble.
      -----

     "Dovey LLC" has the meaning set forth with respect thereto in the preamble.
      ---------

     "Equity Purchase Agreement" means that certain Second Amended and Restated
      -------------------------
Equity Purchase Agreement dated as of the date hereof, by and between the
Company, the Investors, and the other Persons listed on the signature pages
thereto, as amended from time to time in accordance with its terms.

     "Executive Securities Agreements" has the meaning set forth with respect
      -------------------------------
thereto in the Equity Purchase Agreement.

     "First Amended Agreement" has the meaning set forth with respect thereto in
      -----------------------
the preamble.

                                     -11-
<PAGE>

     "Holland" has the meaning set forth with respect thereto in the preamble.
      -------

     "Hundt" has the meaning set forth with respect thereto in the preamble.
      -----

     "Investor" and "Investors" have the meaning set forth with respect thereto
      --------       ---------
in the preamble.

     "Initial Public Offering" means a sale of Common Stock to the public
      -----------------------
registered under the Securities Act on Form S-1 or any similar form.

     "Karafiol" has the meaning set forth with respect thereto in the preamble.
      --------

     "Kirsch" has the meaning set forth with respect thereto in the preamble.
      ------

     "Lacey" has the meaning set forth with respect thereto in the preamble.
      -----

     "Laub" has the meaning set forth with respect thereto in the preamble.
      ----

     "LLC Agreement" means that certain limited liability company agreement
      -------------
governing the affairs of the Company, by and among the Investors and the other
holders of unit membership interests in the Company, as amended from time to
time in accordance with its terms.

     "Long-Form Registration" has the meaning set forth with respect thereto in
      ----------------------
Section 1(a).

     "MDCP" has the meaning set forth with respect thereto in the preamble.
      ----

     "MDCP Registrable Securities" means Registrable Securities derived from or
      ---------------------------
relating to the Preferred Units issued to MDCP under the Equity Purchase
Agreement.

     "Meritage" has the meaning set forth with respect thereto in the preamble.
      --------

     "Meritage Registrable Securities" means Registrable Securities derived from
      -------------------------------
or relating to the Preferred Units issued to Meritage under the Equity Purchase
Agreement.

     "NASD" has the meaning set forth with respect thereto in Section 4(f).
      ----

     "Northwestern" has the meaning set forth with respect thereto in the
      ------------
preamble.

     "Pearson" has the meaning set forth with respect thereto in the preamble.
      -------

     "Pearson LLC #2" has the meaning set forth with respect thereto in the
      --------------
preamble.

                                      -12-
<PAGE>

     "Performance Vesting Agreement" means that certain Second Amended and
      -----------------------------
Restated Performance Vesting Agreement dated as of the date hereof, by and
between the Company, the Investors, and the other Persons listed on the
signature pages thereto, as amended from time to time in accordance with its
terms.

     "Person" means an individual, a partnership, a corporation, a limited
      ------
liability company, an association, a joint stock company, a trust, a joint
venture, an unincorporated organization and a governmental entity or any
department, agency or political subdivision thereof.

     "Piggyback Registration" has the meaning set forth with respect thereto in
      ----------------------
Section 2(a).

     "Preferred Units" means the Preferred Units of the Company, having the
      ---------------
rights and preferences set forth with respect thereto in the LLC Agreement.

     "Prior Agreement" has the meaning set forth with respect thereto in the
      ---------------
preamble.

     "Purchaser Registrable Securities" means Registrable Securities derived
      --------------------------------
from or relating to the Preferred Units issued to the Investors and the other
purchasers under the Equity Purchase Agreement.

     "Registrable Securities" means (i) any Common Stock issued upon conversion
      ----------------------
of any Preferred Units issued under the Equity Purchase Agreement, (ii) any
Common Stock issued under the Executive Securities Agreements (other than any
Un-Performance-Vested Securities), (iii) any Common Stock issued or issuable
with respect to the securities referred to in clauses (i) and (ii) by way of a
stock dividend or stock split or in connection with a combination of shares,
recapitalization, merger, consolidation or other reorganization, or upon
conversion or exercise of any such securities, and (iv) any other Common Stock
of the Company (other than any Un-Performance-Vested Securities) held by any
holder of Registrable Securities; provided that with respect to any Registrable
                                  --------
Securities, such securities shall cease to be Registrable Securities when they
have been (A) effectively registered under the Securities Act and disposed of in
accordance with the registration statement covering them, (B) distributed to the
public through a broker, dealer or market maker pursuant to Rule 144 under the
Securities Act (or any similar rule promulgated by the Securities and Exchange
Commission then in force), (C) distributed to a partner of MDCP or Meritage and
become eligible to be sold by such partner pursuant to Rule 144(k) of the
Securities Act (or any similar rule promulgated by the Securities and Exchange
Commission then in force), or (D) repurchased or otherwise acquired by the
Company (or its assignees) or forfeited pursuant to the terms of the Performance
Vesting Agreement. For purposes of this Agreement, a Person shall be deemed to
be the holder of Registrable Securities, and the Registrable Securities shall be
deemed to be outstanding and in existence, whenever such Person has the right to
acquire such Registrable Securities upon conversion of preferred stock,
Preferred Units, or similar securities held by such Person, whether or not such
acquisition has actually been effected, and such Person shall be entitled to
exercise the rights of a holder of such Registrable Securities hereunder.

                                      -13-
<PAGE>

     "Registration Expenses" has the meaning set forth with respect thereto in
      ---------------------
Section 5(a).

     "SCI" has the meaning set forth with respect thereto in the preamble.
      ---

     "Securities Act" means the Securities Act of 1933, as amended from time to
      --------------
time.

     "Securityholders Agreement" means that certain Second Amended and Restated
      -------------------------
Securityholders Agreement dated as of the date hereof, by and between the
Company and certain of its securityholders, as amended from time to time in
accordance with its terms.

     "Short-Form Registrations" has the meaning set forth with respect thereto
      ------------------------
in Section 1(a).

     "Subsidiary Initial Public Offering" has the meaning set forth with respect
      ----------------------------------
thereto in Section 9(b)(ii).

     "Un-Performance-Vested Securities" means any Company securities which are
      --------------------------------
subject to performance vesting, but have not yet performance vested, pursuant to
the provisions of the Performance Vesting Agreement.

     9.  Miscellaneous.
         -------------

     (a) No Inconsistent Agreements. The Company shall not hereafter enter into
         --------------------------
any agreement with respect to its securities which is inconsistent with or
violates the rights granted to the holders of Registrable Securities in this
Agreement.

     (b) Adjustments Affecting Registrable Securities; Applicability of Rights
         ---------------------------------------------------------------------
to Subsidiaries of the Company.
------------------------------

         (i)  The Company shall not take any action, or permit any change to
     occur, with respect to its securities which would materially and adversely
     affect the ability of the holders of Registrable Securities to include such
     Registrable Securities in a registration undertaken pursuant to this
     Agreement or which would materially and adversely affect the marketability
     of such Registrable Securities in any such registration (including, without
     limitation, effecting a stock split or a combination of shares).

         (ii) In the event that (A) any direct or indirect subsidiary of the
     Company proposes to sell any of its common equity securities to the public
     in a registered offering on Form S-1 under the Securities Act (or any
     similar form) (a "Subsidiary Initial Public Offering"), or (B) the holders
                       ----------------------------------
     of a majority of the Purchaser Registrable Securities then outstanding
     request a Subsidiary Initial Public Offering, then each holder of
     Registrable Securities shall vote all such holder's Registrable Securities
     and any other voting securities of the Company or its subsidiaries over
     which such holder has voting control and shall take

                                      -14-
<PAGE>

     all other necessary or desirable actions within such holder's control
     (whether in such holder's capacity as a securityholder, director,
     representative, member of a board committee, officer of the Company or
     otherwise, and including, without limitation, attendance at meetings in
     person or by proxy for purposes of obtaining a quorum and execution of
     written consents in lieu of meetings), and the Company shall take all
     necessary or desirable actions within its control (including, without
     limitation, calling special board and securityholder meetings and voting
     the securities of its direct and indirect subsidiaries), in each case in
     the manner determined by the holders of a majority of the Purchaser
     Registrable Securities, so that each of the holders of Registrable
     Securities shall be able to exercise and obtain the benefit of its rights
     hereunder (including Demand Registration and Piggyback Registration rights)
     with respect to such subsidiary (including with respect to such Subsidiary
     Initial Public Offering and other registered public offerings of such
     subsidiary's common equity securities) as if such subsidiary were the
     Company.

     (c) Remedies. Any Person having rights under any provision of this
         --------
Agreement shall be entitled to enforce such rights specifically, to recover
damages caused by reason of any breach of any provision of this Agreement and to
exercise all other rights granted by law. The parties hereto agree and
acknowledge that money damages may not be an adequate remedy for any breach of
the provisions of this Agreement and that any party may in its sole discretion
apply to any court of law or equity of competent jurisdiction (without posting
any bond or other security) for specific performance and for other injunctive
relief in order to enforce or prevent violation of the provisions of this
Agreement.

     (d) Amendments and Waivers. Except as otherwise provided herein, the
         ----------------------
provisions of this Agreement may be amended or waived only upon the prior
written consent of the Company and the holders of a majority of the Purchaser
Registrable Securities then outstanding; provided that if any such amendment or
                                         --------
waiver would adversely affect any holder of Registrable Securities relative to
the holders of Registrable Securities voting in favor of such amendment or
waiver, such amendment or waiver shall also require the approval of the holders
of a majority of the Registrable Securities held by all holders so adversely
affected; and provided further that if any such amendment or waiver is to a
          --------------------
provision in this Agreement that requires a specific vote to take an action
thereunder or to take an action with respect to the matters described therein,
such amendment or waiver shall not be effective unless such vote is obtained
with respect to such amendment or waiver.

     (e) Successors and Assigns. All covenants and agreements in this Agreement
         ----------------------
by or on behalf of any of the parties hereto shall bind and inure to the benefit
of the respective successors and assigns of the parties hereto whether so
expressed or not. In addition, whether or not any express assignment has been
made, the provisions of this Agreement which are for the benefit of purchasers
or holders of Registrable Securities are also for the benefit of, and
enforceable by, any subsequent holder of Registrable Securities.

                                      -15-
<PAGE>

     (f) Severability. Whenever possible, each provision of this Agreement shall
         ------------
be interpreted in such manner as to be effective and valid under applicable law,
but if any provision of this Agreement is held to be prohibited by or invalid
under applicable law, such provision shall be ineffective only to the extent of
such prohibition or invalidity, without invalidating the remainder of this
Agreement.

     (g) Counterparts. This Agreement may be executed simultaneously in two or
         ------------
more counterparts, any one of which need not contain the signatures of more than
one party, but all such counterparts taken together shall constitute one and the
same Agreement. Any management or other key employee of the Company or its
subsidiaries who purchases securities pursuant to an Executive Securities
Agreement may at any time after the date hereof, with the written approval of
the Company, become a party to this Agreement by executing a counterpart to this
Agreement agreeing to be bound by the provisions hereof as if such Person were
an original signatory hereto (which joinder shall not constitute an amendment,
modification, or waiver hereof).

     (h) Descriptive Headings; Interpretation; No Strict Construction. The
         ------------------------------------------------------------
descriptive headings of this Agreement are inserted for convenience only and do
not constitute a substantive part of this Agreement. Whenever required by the
context, any pronoun used in this Agreement shall include the corresponding
masculine, feminine or neuter forms, and the singular forms of nouns, pronouns,
and verbs shall include the plural and vice versa. Reference to any agreement,
document, or instrument means such agreement, document, or instrument as amended
or otherwise modified from time to time in accordance with the terms thereof,
and if applicable hereof. The use of the words "include" or "including" in this
Agreement shall be by way of example rather than by limitation. The use of the
words "or," "either" or "any" shall not be exclusive. The parties hereto have
participated jointly in the negotiation and drafting of this Agreement. If an
ambiguity or question of intent or interpretation arises, this Agreement shall
be construed as if drafted jointly by the parties hereto, and no presumption or
burden of proof shall arise favoring or disfavoring any party by virtue of the
authorship of any of the provisions of this Agreement.

     (i) Governing Law. All issues and questions concerning the construction,
         -------------
validity, interpretation and enforcement of this Agreement and the exhibits and
schedules hereto shall be governed by, and construed in accordance with, the
laws of the State of Delaware, without giving effect to any choice of law or
conflict of law rules or provisions (whether of the State of Delaware or any
other jurisdiction) that would cause the application of the laws of any
jurisdiction other than the State of Delaware.

     (j) Notices. All notices, demands or other communications to be given or
         -------
delivered under or by reason of the provisions of this Agreement shall be in
writing and shall be deemed to have been given when (a) delivered personally to
the recipient, (b) telecopied to the recipient (with hard copy sent to the
recipient by reputable overnight courier service (charges prepaid) that same
day) if telecopied before 5:00 p.m. Chicago, Illinois time on a business day,
and otherwise on the next business day, or (c) one business day after being sent
to the recipient by reputable overnight courier service (charges prepaid). Such
notices, demands and other

                                      -16-
<PAGE>

communications shall be sent to the Company at the address set forth below and
to any holder of Registrable Securities at such address as indicated by the
Company's records, or at such address or to the attention of such other person
as the recipient party has specified by prior written notice to the sending
party. The Company's address is:

                  6300 Syracuse Way, Suite 355
                  Englewood, Colorado 80111
                  Attention:    Chief Executive Officer
                  Telephone:    (303) 741-4788
                  Telecopy:     (303) 741-4823

     (k) Business Days. If any time period for giving notice or taking action
         -------------
hereunder expires on a day which is a Saturday, Sunday or legal holiday in the
State of Colorado, the Republic of France, or the jurisdiction in which the
Company's principal office is located, the time period shall automatically be
extended to the business day immediately following such Saturday, Sunday or
legal holiday.

     (l) Delivery by Facsimile. This Agreement, the agreements referred to
         ---------------------
herein, and each other agreement or instrument entered into in connection
herewith or therewith or contemplated hereby or thereby, and any amendments
hereto or thereto, to the extent signed and delivered by means of a facsimile
machine, shall be treated in all manner and respects as an original agreement or
instrument and shall be considered to have the same binding legal effect as if
it were the original signed version thereof delivered in person. At the request
of any party hereto or to any such agreement or instrument, each other party
hereto or thereto shall reexecute original forms thereof and deliver them to all
other parties. No party hereto or to any such agreement or instrument shall
raise the use of a facsimile machine to deliver a signature or the fact that any
signature or agreement or instrument was transmitted or communicated through the
use of a facsimile machine as a defense to the formation or enforceability of a
contract and each such party forever waives any such defense.

     (m) Effectiveness of Agreement. This Agreement shall be valid, binding, and
         --------------------------
effective against each holder of Registrable Securities when it has been signed
by such holder. Pursuant to Section 9(d) of the First Amended Agreement, this
Agreement amending and restating the First Amended Agreement shall be valid,
binding, and effective against all holders of Registrable Securities when it has
been signed by the holders of a majority of the Purchaser Registrable
Securities.

                                    * * * * *

                                      -17-
<PAGE>

     IN WITNESS WHEREOF, the parties hereto have executed this Second Amended
and Restated Registration Agreement as of the date first written above.

                      COMPLETEL, LLC

                      By  /s/ James E. Dovey
                          --------------------------------------------
                               James E. Dovey, its Chairman and CEO


                      DEGEORGE HOLDINGS LIMITED PARTNERSHIP

                      By LPL Investment Group, Inc., its general partner

                      By  /s/ Lawrence F. DeGeorge
                          ------------------------------------------
                               Lawrence F. DeGeorge, its Chairman


                      MADISON DEARBORN CAPITAL PARTNERS II, L.P.

                      By Madison Dearborn Partners II, L.P., its general partner
                      By Madison Dearborn Partners, Inc., its general partner

                      By  /s/ Paul J. Finnegan
                          ------------------------------------------

                      Its   Managing Director
                            ------------------------------------------


                      MERITAGE PRIVATE EQUITY FUND, L.P.

                      By Meritage Investment Partners, LLC, its general partner

                      By: /s/ Laura J. Beller
                          -------------------------------------------
                               Managing Member

                      /s/ James C. Allen
                      ---------------------------------------------
                      James C. Allen


                      /s/ Royce J. Holland
                      ---------------------------------------------
                      Royce J. Holland


(Signature page for Second Amended and Restated Registration Agreement)
<PAGE>

                      /s/ George T. Laub
                      ---------------------------------------------
                      George T. Laub

                      /s/ Reed E. Hundt
                      ----------------------------------------------
                       Reed E. Hundt



                      DOVEY FAMILY PARTNERS LLLP


                      By  /s/ James E. Dovey
                          -----------------------------------------
                               James E. Dovey, its general partner


                      DOVEY COMPANY LLC


                      By  /s/ James E. Dovey
                          -----------------------------------------
                               James E. Dovey, its manager


                      /s/ James E. Dovey
                      ---------------------------------------------
                      James E. Dovey


                      /s/ William H. Pearson
                      ---------------------------------------------
                      William H. Pearson


                      /s/ Richard N. Clevenger
                      ---------------------------------------------
                      Richard N. Clevenger


                      /s/ David E. Lacey
                      ---------------------------------------------
                      David E. Lacey



(Signature page for Second Amended and Restated Registration Agreement)
<PAGE>

                      HAJ PEARSON LLC


                      By  /s/ William H. Pearson
                          -----------------------------------------
                               William H. Pearson, its manager



                      HAJ LLC


                      By  /s/ William H. Pearson
                          -----------------------------------------
                               William H. Pearson, its manager



                      CLEVENGER COMPANY LLC


                      By  /s/ Richard N. Clevenger
                          -----------------------------------------
                               Richard N. Clevenger, its manager



                      CLEVENGER FAMILY LLLP


                      By  /s/ Richard N. Clevenger
                          -----------------------------------------
                          Richard N. Clevenger, its general partner



(Signature page for Second Amended and Restated Registration Agreement)
<PAGE>

                       /s/ Emile Karafiol
                      ---------------------------------------------
                      Emile Karafiol

                      /s/ William S. Kirsch
                      ---------------------------------------------
                      William S. Kirsch


                      NORTHWESTERN UNIVERSITY


                      By  /s/ David L. Wagner
                          ------------------------------------------

                      Its VP and CIO
                          ------------------------------------------


                      SILVER CROSS INVESTORS LLC


                      By  /s/ Jeffrey W. Richards
                          ------------------------------------------

                      Its Manager
                          ------------------------------------------


(Signature page for Second Amended and Restated Registration Agreement)
<PAGE>

                      OTHER MEMBERS (SIGNATURES OF WHOM
                      ARE NOT INCLUDED) WHO ARE PARTY TO
                      THIS AGREEMENT PURSUANT TO THEIR
                      EXECUTIVE SECURITIES AGREEMENTS
                      (AND/OR JOINDER AGREEMENTS ENTERED
                      INTO IN CONNECTION THEREWITH):
                      ----------------------------------------------------------


                      Richard Folliot            John Hugo
                      Anna Lascar                Hughes Le Masne
                      Jean-Marie Le Monze        Gerd Menhorn
                      Charles Menatti            Martin Rushe
                      John Seder                 Jean Rodriguez
                      Alexandre Westphalen       Gerhard Burtscher
                      Nicolas Pitance            Jean Francois Bouchaud
                      Claude LeMaire             Ralf Heydtmann
                      Michel Picariello          D. Werner Grum
                      Frank Lauterslager         Wolfgang Brauneis
                      John Puhl                  Peter Chalupny
                      Harold F. Carey, Jr.       Anton Matos
                      Guy Gensollen              Michael Hulm
                      Pierre Wattelier           Markus Lackermaier
                      Hansjorg Rieder
                      Jean-Francois Golhen
                      Jerome de Vitry
                      Martine Clarkson
                      Chantal Lebon
                      Marie LeCocq
                      Anne-Catherine Nicosia
                      Valerie Hotte
                      Marie-Christine Boudin
                      Van-Linh Siharath
                      Isabelle Dubien
                      Nadege Griffit
                      Gregory Burlinchon
                      Cecile Affret
                      Jean Rodriguez
                      Catherine Grosjean
                      Kathleen Hanlon



(Signature page for Second Amended and Restated Registration Agreement)