<PAGE>

                                                                   Exhibit 10.42

             Regulatory Authority for Telecommunications and Post



                                 Licence Deed
<PAGE>

                                                                   Seite 1 von 4

                                Licence Class 3


                    for the operation of transmission lines
                 for the offer of telecommunications services
                for the public by the licensee or other parties



The Regulatory Authority for Telecommunications and Post (RegTP) - in the
following "licensor" - herewith grants pursuant to the application dated 27.
March 2000 on the basis of sec. 6 para. 1 no. 1, para. 2 no. 1 c) in connection
with sec. 8 para. 1 to 3 and Sec. 50 para. 2 sentence 1 of the
Telecommunications Act (TKG) of 25 July 1996 (Federal Law Gazette I, p. 1120) to
the company


                                Comple Tel GmbH

                   Maximilianstra(BETA)e 35A, 80539 Munchen


(in the following "licensee) a licence class 3 for the operation of transmission
lines for the provision of telecommunications services for the public by the
licensee or third parties.

The application dated 27. March 2000 is part of this licence.

The licence is registered under 98 03 1070.
<PAGE>

                                                                   Seite 2 von 4

1.  Licence Object

1.1 Material Scope

    With this licence the licensee is granted the right pursuant to the
    Telecommunications Act and ordinances basing thereon, within the scope of
    the licence class 3, to operate transmission lines for the provision of
    telecommunications services for the public by the licensee or third parties.

    The licensee is entitled to operate wireless transmission lines if the
    required frequency spectrum has been allocated pursuant to sec. 44 to 48 TKG
    and the frequency ordinances basing thereon. The frequency allocations will
    become part of this licence.

    The licence does not entitle to the provision of voice telephony services
    (sec. 6 para. 2 no. 2 TKG), the operation of transmission lines for mobile
    telecommunications services or satellite communications services for the
    public (Sec. 6 para. 2 no. 1 a) and b) TKG).

1.2 Regional Scope

    The licence encompasses the following area:

    Cities in the administrative district of Stuttgart
    --------------------------------------------------

    .  Asperg                   .  Korntal-Munchingen           .  Moglingen
    .  Ditzingen                .  Kornwestheim                 .  Ostfildern
    .  Esslingen am Neckar      .  Leinfelden-Echterdingen      .  Sindelfingen
    .  Fellbach                 .  Leonberg                     .  Stuttgart
    .  Gerlingen                .  Ludwigsburg

2   Use of Traffic Ways

    The licensor pursuant to sec. 50 para. 2 sentence 1 TKG transfers to the
    licensee the right to use public traffic ways free of charge for
    telecommunications lines (sec. 3 no. 20 TKG) which it requires to use the
    rights granted by the licence pursuant to sec. 50 to 58 TKG in such a way
    that the dedicated purpose of the traffic way is not thereby restricted on
    an ongoing basis.

3   Conditions

3.1 Changes in the Commercial Register

    Changes in the commercial register have to be notified to the licensor
    immediately with an certified excerpt from the commercial register being
    attached. This information is required to assess whether the licence
    conditions pursuant to sec. 8 para. 3 sentence 2 no. 2 TKG are still met and
    in order to secure that the obligations in case of a change of the licensee
    and/or a change in the ownership of the licensee pursuant to sec. 9 TKG are
    met.
<PAGE>

                                                                   Seite 3 von 4

3.2 Offer of Transmission Ways

    The offer of transmission ways pursuant to exhibit 2 of the Council
    Directive 92/44/EC dated 5 June 1992 regarding the provision of open network
    access in respect of leased lines (OJ EC no. L 165 dated 19 June 1992, p.
    27) amended by Commission decision 94/439/EC dated 15 June 1994 (OJ EC no. L
    181 dated 15 July 1994, p. 40) has to be notified to the licence
    immediately. This information is required in order to determine the market
    share in accordance with the universal services obligation pursuant to sec.
    18 para. 1 TKG.


3.3 Security Commissioner and Documentation Pursuant to Sec. 87 para. 2 TKG

    The licensee is obliged, prior to the start of operation, to nominate a
    security commissioner, to submit the documentation mentioned in sec. 87
    para. 2 TKG and to submit the declaration pursuant to sec. 87 para. to
    sentence to TKG.

4   Note

4.1 Technical Implementation of Intercepts

    Please note, that the technical configuration of systems to implement the
    required measures for interception of telecommunication pursuant to sec. 88
    para. 2 sentence 1 requires the approval of the Regulatory Authority. The
    start of operation of telecommunications systems prior to the proof within
    the scope of the final inspection that the requirements have been met is
    prohibited pursuant to sec. 88 para. 2 sentence 4 in connection with sec. 96
    para. 1 no. 13 and 14 TKG and may in connection with sec. 15 TKG trigger the
    withdrawal of the licence.

    The configuration and provision of technical facilities to implement legally
    prescribed measures for the interception of telecommunications are not
    required,

    .    provided the termination points of the transmission lines, which are
         allocated within the regional scope of this licence are connected only
         to nodes whose operators themselves are bound by sec. 88 TKG, or
         provided the transmission lines only serve the connection between nodes
         to which termination equipment pursuant to sec. 2 no. 4 FUV or pursuant
         to the ordinance based on sec. 88 para. 2 TKG may not be connected.

    .    provided the licensee only operates transmission lines exclusively for
         the transmission of audio and broadcasting signals without return
         channel for the public by itself or a third party.

4.2 Licence Fees

    The licence will be granted for a fee pursuant to sec. 16 para. 1 sentence 1
    TKG. The determination of the fees pursuant to the Telecommunications
    Licence Fee Ordinance (TKLGebV) dated 28 July 1997 (Federal Gazette I p.
    1936) which bases on sec. 16 para. 1 sentence 2 TKG will be made by separate
    administrative act.
<PAGE>

                                                                   Seite 4 von 4

4.3 Frequency Fees and Contributions

    Costs related to a possible allocation of frequency spectrum will be payable
    pursuant to sec. 48 TKG and the Frequency Fee Ordinance (FGebV) dated 21 May
    1997 (Federal Gazette I, p. 1126) in connection with the first order to
    modify the Frequency Fee Ordinance dated 16 December 1997 (Federal Gazette
    I, p. 3194) and the Frequency Contribution Ordinance (FBeitrV) dated 19
    November 1996 (Federal Gazette I, p. 1790) in connection with the first
    order to modify the Frequency Contribution Ordinance dated 12 December 1998
    (Federal Gazette I p. 3894). Frequency fees and frequency contributions are
    determined by separate administrate of act. Changes to the allocation and
    new allocation of spectrum will be made by separate administrative act.

4.4 Transmission of Broadcasting Programs
    In case of the operation of transmission lines for which the allocation of
    frequency spectrum for the transmission of broadcasting programs is
    required, please note that sec. 47 para. 3 TKG will apply.

4.5 Ex-Post Modification of the Conditions
    Pursuant to sec. 8 para. 2 sentence 2 TKG the conditions to this licence may
    be amended even after the grant of the licence.

4.6 Miscellaneous
    Please note that all further provisions of the TKG will apply.


                     Instruction about the Right to Appeal

Within one month of announcing this notification, legal proceedings may be
instituted, in writing or to be recorded by the court divisions registrar, at
the Verwaltungsgericht Koln, Appellhofplatz, 50667 Koln (The Administrate of
Court of Cologne). The legal 7brief must state the plaintiff, the defendant and
the subject of the complaint. It must contain a definite motion. The fact and
evidence serving as substantiation must be stated. The legal brief and its
exhibits must be accompanied by as many copies as are needed to give each
participant one copy. The legal action has no suspensive effect.



Regulatory Authority for
Telecommunications and Post                     Mainz, 07. July 2000


Signed and Stamped:


Zufall