<PAGE>

                                                                   Exhibit 10.36

             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 1066.
<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 Karlsruhe
     --------------------------------------------------

     .  Edingen-Neckarhausen       .  Ilvesheim       .  Mannheim
     .  Eppelheim                  .  Ldenburg        .  Sandhausen
     .  Heidelberg                 .  Leimen

     Cities in the administrative district of Rheinhessen-Pfalz
     ----------------------------------------------------------

     .  Ludwigshafen am Rhein

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