ALLEGIANCE TELECOM INC
8-K, 1999-09-22
TELEPHONE COMMUNICATIONS (NO RADIOTELEPHONE)
Previous: EQUITRUST LIFE ANNUITY ACCOUNT II, 497, 1999-09-22
Next: CMP GROUP INC, DEFA14A, 1999-09-22



<PAGE>   1
================================================================================


                UNITED STATES SECURITIES AND EXCHANGE COMMISSION
                              WASHINGTON, DC 20549


                                    FORM 8-K


                                 CURRENT REPORT

     Pursuant to Section 13 or 15(d) of the Securities Exchange Act of 1934


      Date of report (Date of earliest event reported): September 13, 1999



                            ALLEGIANCE TELECOM, INC.
             (EXACT NAME OF REGISTRANT AS SPECIFIED IN ITS CHARTER)


                                    Delaware
                            (State of Incorporation)


        0-24509                                           75-2721491
(Commission File Number)                       (IRS Employer Identification No.)



                              1950 Stemmons Freeway
                                   Suite 3026
                               Dallas, Texas 75207
                                 (214) 261-7100
               (Address of Principal Executive Offices) (Zip Code)
              (Registrant's Telephone Number, Including Area Code)


================================================================================



<PAGE>   2


ITEM 5. OTHER EVENTS.

         The terms of the transaction summarized below are more specifically set
forth in the Common Stock Purchase and Option Agreement, Counterpart Agreement,
Investors Agreement and Amended and Restated Registration Agreement, which are
attached as exhibits to this Current Report on Form 8-K.

         Purchase Agreement. On September 13, 1999, Vulcan Ventures Incorporated
purchased an aggregate of 1.5 million shares of Allegiance Telecom common stock
from Madison Dearborn Capital Partners II, L.P., Frontenac VII Limited
Partnership, Frontenac Masters VII Limited Partnership, Battery Ventures IV,
L.P., Battery Investment Partners IV, LLC, Reed E. Hundt (a director of
Allegiance Telecom) and Gregory E. Lawler. The aggregate purchase price for such
shares was $75 million. Immediately following the closing of this purchase,
Vulcan Ventures owned approximately 2.3% of the outstanding common stock of
Allegiance Telecom.

         The Common Stock Purchase and Option Agreement also grants Vulcan
Ventures an option to purchase up to an additional 5 million shares, at $56 per
share, on or before November 1, 1999, from existing private equity investors and
certain other investors. If Vulcan Ventures exercises the option in full, based
on the current number of shares outstanding, Vulcan will own 10% of the
outstanding common stock of Allegiance Telecom. Allegiance Telecom will not
receive any cash from either the 1.5 million share transaction or the option
transaction.

         Investors Agreement. Allegiance Telecom has agreed to use its best
efforts to cause (a) one designee nominated by Vulcan Ventures to be appointed
to the board of Allegiance Telecom (the "Board"), for so long as Vulcan Ventures
continues to hold at least 1.2 million shares (as adjusted for stock dividends,
stock splits and other recapitalizations) of Allegiance Telecom common stock,
and (b) two designees nominated by Vulcan Ventures to be appointed to the Board,
if Vulcan Ventures acquires at least 2.5 million shares under the option, and so
long as Vulcan continues to hold at least 4 million shares (in each case as
adjusted for stock dividends, stock splits and other recapitalizations) of such
stock. This right to designate a director is not assignable by Vulcan Ventures.

         Vulcan Ventures has agreed with Allegiance Telecom not to offer, sell,
transfer or otherwise dispose of any of the Investor Shares (as such term is
defined in the Investors Agreement) prior to September 13, 2000 without the
prior written consent of the Board; provided that Vulcan Ventures may pledge
such shares and transfer such shares to and among its affiliates and provided
that such restriction on transfers shall terminate upon and with respect to the
consummation of a "Sale of the Company" (as such term is defined in the
Investors Agreement).

         During the "Standstill Period," Vulcan Ventures has agreed that it and
its affiliates and associates will not, directly or indirectly, among other
things: (i) acquire any of the voting securities (or securities convertible or
exchangeable into or exercisable for any voting securities) of Allegiance
Telecom or any of its subsidiaries or other affiliates, (ii) acquire any assets
of Allegiance Telecom or any of its subsidiaries or other affiliates, or (iii)
participate in any tender offer, exchange offer, merger, business combination or
other extraordinary transaction involving Allegiance Telecom or any of its
subsidiaries or other affiliates; provided that with respect to the foregoing
clauses (i) through (iii), Vulcan Ventures may take any of such actions within
60 days after another person that is not an affiliate or associate of Vulcan
Ventures has made a publicly announced proposal to take any such action that
would result in a "Sale of the Company" (as


                                       1
<PAGE>   3

such term is defined in the Investors Agreement), so long as Vulcan's actions
are not in concert with such other person. Notwithstanding the foregoing, Vulcan
Ventures and its affiliates and associates may acquire ownership of Allegiance
Telecom's securities such that Vulcan Ventures and its affiliates and associates
would own, directly or indirectly, not more than 20% of Allegiance Telecom's
then outstanding voting securities. In addition, during the Standstill Period,
Vulcan Ventures has agreed that it and its affiliates and associates will not,
directly or indirectly, among other things: (i) become a member of a group with
respect to the common stock or other equity securities or assets of Allegiance
Telecom; (ii) call or seek to call any special meeting of or initiate a
stockholder vote or action by written consent of the Company's stockholders;
(iii) participate in any "solicitation" of "proxies" to vote, or seek to
influence any person or entity with respect to Allegiance Telecom in opposition
to any matter which has been recommended by the Board or in favor of any matter
which has not been approved by the Board; or (iv) enter into any discussions,
negotiations, arrangements or understandings with any third party with respect
to any of the foregoing. "Standstill Period" means the period beginning on
September 13, 1999 and ending upon the first to occur of (i) the closing of a
"Sale of the Company" (as such term is defined in the Investors Agreement) or
(ii) the date after September 13, 2002 on which Vulcan has not for 180 days had
a representative serving on the Board (and has waived or otherwise lost its
rights hereunder to have such a representative).

         Amended and Restated Registration Agreement.

         At any time after September 13, 2000, Vulcan Ventures is entitled to
demand one long-form registration, such as registration on Form S-1, and two
short-form registrations, such as registration on Form S-3, with respect to the
shares purchased by Vulcan under the Common Stock Purchase and Option Agreement.
In addition, Vulcan Ventures may "piggyback" on primary or secondary registered
public offerings of Allegiance's securities. Allegiance has agreed to pay the
registration expenses in connection with these demand and "piggyback"
registrations.

         Vulcan Ventures has agreed not to effect a public sale or distribution
of any equity securities of Allegiance (including any securities convertible
into, or exercisable or exchangeable for such securities) during the seven days
prior to and the 90 day period following the effective date of any other
underwritten demand registration or underwritten piggyback registration, unless
the managing underwriters otherwise agree.


ITEM 7. FINANCIAL STATEMENTS AND EXHIBITS.

(a) - (b)         None.

(c) The exhibits filed in response to Item 601 of Regulation S-K are listed in
the Exhibit Index starting on page E-1 of this report.


                                       2

<PAGE>   4



                                   SIGNATURES

According to the requirements of the Securities Exchange Act of 1934, Allegiance
Telecom, Inc. has duly caused this report to be signed on its behalf by the
undersigned, thereunto duly authorized on September 22, 1999.


                                      ALLEGIANCE TELECOM, INC.

                                      By  /s/ MARK B. TRESNOWSKI
                                      ------------------------------------------
                                      Mark B. Tresnowski
                                      Senior Vice President, General Counsel and
                                      Secretary


                                       3
<PAGE>   5


                                  EXHIBIT INDEX


<TABLE>
<CAPTION>
   EXHIBIT
     NO.                                DESCRIPTION
   -------                              -----------
<S>              <C>
     99.1        Common Stock Purchase and Option Agreement, dated August 3,
                 1999, among Madison Dearborn Capital Partners II, L.P.,
                 Frontenac VII Limited Partnership, Frontenac Masters VII
                 Limited Partnership, Battery Ventures IV, L.P., Battery
                 Investment Partners IV, LLC, Allegiance Telecom, Inc. and
                 Vulcan Ventures Incorporated

     99.2        Counterpart Agreement, dated September 13, 1999, among Madison
                 Dearborn Capital Partners II, L.P., Frontenac VII Limited
                 Partnership, Frontenac Masters VII Limited Partnership,
                 Battery Ventures IV, L.P., Battery Investment Partners IV,
                 LLC, Reed E. Hundt and Gregory E. Lawler

     99.3        Investors Agreement, dated September 13, 1999, between
                 Allegiance Telecom, Inc. and Vulcan Ventures Incorporated

     99.4        Amended and Restated Registration Agreement, dated September
                 13, 1999, among Allegiance Telecom, Inc., Battery Ventures IV,
                 L.P., Battery Investment Partners IV, LLC, Frontenac VII
                 Limited Partnership, Frontenac Masters VII Limited Partnership,
                 Madison Dearborn Capital Partners II, L.P., Morgan Stanley
                 Capital Partners III, L.P., MSCP III 892 Investors, L.P.,
                 Morgan Stanley Capital Investors, L.P., Vulcan Ventures
                 Incorporated and certain other stockholders listed therein
</TABLE>

                                      E-1

<PAGE>   1
                                                                   EXHIBIT 99.1






                       ---------------------------------

                   COMMON STOCK PURCHASE AND OPTION AGREEMENT

                                  By and Among

                  MADISON DEARBORN CAPITAL PARTNERS II, L.P.,

                       FRONTENAC VII LIMITED PARTNERSHIP,

                   FRONTENAC MASTERS VII LIMITED PARTNERSHIP,

                           BATTERY VENTURES IV, L.P.,

                      BATTERY INVESTMENT PARTNERS IV, LLC,

                            ALLEGIANCE TELECOM, INC.

                                      and

                          VULCAN VENTURES INCORPORATED


                             Dated: August 3, 1999

                       ---------------------------------



Purchase Agreement Final
<PAGE>   2

                   COMMON STOCK PURCHASE AND OPTION AGREEMENT


                  THIS COMMON STOCK PURCHASE AND OPTION AGREEMENT (this
"AGREEMENT") is made and entered into as of August 3, 1999, among Vulcan
Ventures Incorporated, a Washington corporation ("BUYER"), and the parties
listed on Schedule I hereto (individually, a "SELLER" and collectively,
"SELLERS").

                  Sellers own shares of Common Stock, par value $.01 per share
(the "COMMON STOCK"), of Allegiance Telecom, Inc., a Delaware corporation
("ALLEGIANCE"), and Sellers desire to sell certain of such shares to Buyer, and
Buyer desires to purchase such shares from Sellers pursuant to the terms and
conditions of this Agreement. In addition, Sellers desire to grant to Buyer the
option to purchase additional shares of Common Stock. All share numbers and
dollar values set forth in this Agreement shall be appropriately adjusted after
the date hereof to take into account any stock dividends, stock splits and
other recapitalizations.

                  In consideration of the premises and the mutual promises
herein made, and in consideration of the representations, warranties, and
covenants herein contained, the parties hereto agree as follows:

                  1. Purchase and Sale of Stock. At the Initial Closing (as
defined below) and upon the terms and conditions set forth in this Agreement,
each Seller shall sell, transfer and assign to Buyer, and Buyer shall purchase
from each Seller, all of such Seller's right, title and interest in and to the
number of shares of Common Stock set forth opposite such Seller's name under
the caption "Initial Closing Shares" on Schedule I hereto (the "INITIAL CLOSING
Shares"). The purchase price for each Initial Closing Share shall be $50.00.

                  2. Initial Closing. Subject to the terms and conditions
contained in this Agreement, the purchase and sale of the Initial Closing
Shares hereunder (the "INITIAL CLOSING") shall take place at the offices of
Allegiance Telecom, Inc. at 1950 Stemmons Freeway, Suite 3026, Dallas, TX 75207
as soon as practicable after the satisfaction or waiver of the closing
conditions set forth below, or at such other place or on such other date as is
mutually agreeable to Buyer and Sellers. At the Initial Closing, each Seller
shall deliver to Buyer a stock certificate or certificates representing the
Initial Closing Shares to be sold by such Seller, registered in Buyer's name,
and Buyer shall deliver the aggregate purchase price for the Initial Closing
Shares purchased from each Seller (the aggregate of such funds, the "INITIAL
AGGREGATE PRICE") by wire transfer of immediately available funds to a bank
account designated in writing by such Seller. Each of Buyer and Allegiance
shall (a) promptly, and in any event no less than five business days after the
date hereof, make all required filings under the Hart-Scott-Rodino Antitrust
Improvements Act of 1976, as amended (the "HSR Act") and (b) use its best
efforts to receive early termination of the HSR waiting period.



                                      -1-

Purchase Agreement Final
<PAGE>   3

                  3. Conditions to Obligations at the Initial Closing.

                  (a) The obligation of each Seller to sell, transfer and
assign the Initial Closing Shares to be sold to Buyer hereunder is subject to
the satisfaction of the following conditions as of the Initial Closing:

                             (i) the representations and warranties contained
         in paragraph 8 hereof shall be true and correct at and as of the
         Initial Closing as though then made, except to the extent of changes
         caused by the transactions expressly contemplated herein;

                            (ii) Allegiance and Buyer shall have entered into
         the Investors Agreement substantially in the form attached as Exhibit
         A hereto;

                          (iii) Each other Seller, Buyer and certain Allegiance
         management stockholders shall have entered into the Amended and
         Restated Registration Agreement substantially in the form attached as
         Exhibit B hereto; and

                            (iv) the waiting period under the HSR Act with
         respect to the transactions contemplated by the Initial Closing, shall
         have terminated or expired.

                  (b) The obligation of Buyer to purchase the Initial Closing
Shares from each Seller is subject to the satisfaction of the following
conditions as of the Initial Closing:

                             (i) the representations and warranties contained
         in paragraph 7 shall be true and correct at and as of the Initial
         Closing as though then made, except to the extent of changes caused by
         the transactions expressly contemplated herein;

                            (ii) Allegiance shall have entered into the
         Investors Agreement substantially in the form attached as Exhibit A
         hereto;

                          (iii) Sellers and certain Allegiance management
         stockholders shall have entered into the Amended and Restated
         Registration Agreement substantially in the form attached as Exhibit B
         hereto; and

                            (iv) the waiting period under the HSR Act with
         respect to the transactions contemplated by the Initial Closing, shall
         have terminated or expired.

                  4. Option.

                  (a) Each Seller hereby grants Buyer the option (the "OPTION")
to purchase the number of shares of Common Stock set forth opposite such
Seller's name under the caption "Option Shares" on Schedule I hereto (the
"OPTION SHARES" and together with the Initial Closing Shares, the "SHARES") at
a purchase price of $56.00 per share. In addition, Allegiance agrees to cause
certain management stockholders (other than its Chairman and Chief Executive
Officer or any of his transferees) to sell to Buyer a total of 852,999 shares
(the "MANAGEMENT SHARES") at a purchase



                                      -2-

Purchase Agreement Final
<PAGE>   4

price of $56.00 per share. When used with respect to the Option, the term
"Seller" shall be deemed to include holders of Management Shares. Allegiance
shall cause each such holder to execute a counterpart to this Agreement as a
Seller prior to the Option Closing (as defined in paragraph 5 below).

                  (b) If and when exercised, the Option shall be deemed
exercised with respect to all Sellers in an amount equal to the total number of
Option Shares listed with respect to such Seller on Schedule I hereto
multiplied by a fraction, the numerator of which is the number of shares as to
which the Option has been exercised and the denominator of which is 5,000,000.

                  (c) To exercise the Option, Buyer must provide written notice
to Allegiance and each of the Sellers on or before November 1, 1999 (the
"OPTION EXERCISE DATE" and the period from the date hereof through the Option
Exercise Date, the "OPTION PERIOD") and must exercise the Option for no less
than one million and no more than five million Option Shares. The Option may be
exercised only once and shall expire to the extent not properly exercised on or
before the Option Exercise Date. Upon exercise of the Option, Buyer and Sellers
shall (a) promptly, and in any event no less than two business days thereafter,
make all required filings under the HSR Act and (b) use its best efforts to
receive early termination of the HSR waiting period.

                  (d) At the Option Closing and upon the terms and conditions
set forth in this Agreement, each Seller shall sell, transfer and assign to
Buyer, and Buyer shall purchase from each Seller, all of such Seller's right,
title and interest in and to the number of Option Shares with respect to which
the Option has been exercised.

                  (e) As consideration for the Option, the parties agree that
promptly after the date hereof, Allegiance and Go2Net, Inc. ("GO2NET") shall
enter into good faith negotiations with a view towards establishing a mutually
acceptable strategic alliance. Such negotiations will include, among other
things, a discussion of (i) a customized business portal created by Go2Net for
Allegiance, which will include selected components of Go2Net's Web sites
targeted at Allegiance's end-users, (ii) hosting by Go2Net of the customized
portal, (iii) Go2Net providing the home page on a co-branded basis with
Allegiance and (iv) Go2Net providing the design, hosting and engineering
associated with customizable modules.

                  5. Option Closing. Subject to the terms and conditions
contained in this Agreement, the purchase and sale of the Option Shares
hereunder (the "OPTION CLOSING") shall take place at the offices of Allegiance
Telecom, Inc. at 1950 Stemmons Freeway, Suite 3026, Dallas, TX 75207 as soon as
practicable after the exercise of the Option and the satisfaction or waiver of
the closing conditions set forth below, or at such other place or on such other
date as is mutually agreeable to Buyer and Sellers. At the Option Closing, each
Seller shall deliver to Buyer a stock certificate or certificates representing
the Option Shares to be sold by such Seller, registered in Buyer's name, and
Buyer shall deliver the aggregate purchase price for the Option Shares
purchased from each Seller by wire transfer of immediately available funds to a
bank account designated in writing by such Seller.



                                      -3-

Purchase Agreement Final
<PAGE>   5

                  6. Conditions to Obligations at the Option Closing.

                  (a) The obligation of each Seller to sell, transfer and
assign the Option Shares to be sold to Buyer hereunder is subject to the
satisfaction of the following conditions as of the Option Closing:

                             (i) the representations and warranties contained
         in paragraph 8 hereof shall be true and correct at and as of the
         Option Closing as though then made, except to the extent of changes
         caused by the transactions expressly contemplated herein;

                            (ii) The Investors Agreement substantially in the
         form attached as Exhibit A hereto shall be in full force and effect;

                           (iii) The Amended and Restated Registration Agreement
         substantially in the form attached as Exhibit B hereto shall be in
         full force and effect; and

                            (iv) the waiting period under the HSR Act with
         respect to the transactions contemplated by the Option Closing shall
         have terminated or expired.

                  (b) The obligation of Buyer to purchase the Option Shares
from each Seller is subject to the satisfaction of the following conditions as
of the Option Closing:

                             (i) the representations and warranties contained
         in paragraph 7 shall be true and correct at and as of the Option
         Closing as though then made, except to the extent of changes caused by
         the transactions expressly contemplated herein;

                            (ii) The Investors Agreement substantially in the
         form attached as Exhibit A hereto shall be in full force and effect;

                           (iii) The Amended and Restated Registration Agreement
         substantially in the form attached as Exhibit B hereto shall be in
         full force and effect; and

                            (iv) the waiting period under the HSR Act with
         respect to the transactions contemplated by the Option Closing shall
         have terminated or expired.

                  7. Representations and Warranties of Each Seller. Each Seller
hereby represents and warrants to Buyer as follows:

                  (a) Organization; Authorization. Seller is duly organized,
validly existing, and in good standing under the laws of the jurisdiction of
its formation. Seller has full power and authority to execute and deliver this
Agreement and to perform its obligations hereunder. The execution and
performance of this Agreement have been duly authorized by all necessary action
on the part of Seller, and this Agreement when executed and delivered shall
constitute a valid and legally binding obligation of Seller, enforceable in
accordance with its terms, except as enforceability may be limited by
bankruptcy, similar laws of debtor relief and general principles of equity.



                                      -4-

Purchase Agreement Final
<PAGE>   6

                  (b) Ownership. All of the Shares set forth opposite such
Seller's name on Schedule I hereto are owned of record and beneficially by such
Seller, and such Seller has good and marketable title to such Shares. At the
Initial Closing and the Option Closing, if applicable, such Seller will
transfer to Buyer good and marketable title to such Shares, free and clear of
all security interests, claims, liens, pledges, options, encumbrances, charges,
agreements, voting trusts, proxies and other arrangements or restrictions
whatsoever. All of such Shares are validly issued, fully paid and
nonassessable.

                  (c) Conflicts. The execution, delivery and performance of
this Agreement by such Seller does not conflict with, violate or result in the
breach of, or create any lien or encumbrance on its Shares pursuant to, any
agreement, instrument, order, judgment, decree, law or governmental regulation
to which such Seller is a party or is subject or by which its Shares are bound.

                  (d) Brokers' Fees. Seller has no liability or obligation to
pay any fees or commissions to any broker, finder, or agent with respect to the
transactions contemplated by this Agreement for which Buyer or any other party
could become liable or otherwise obligated.

                  8. Representations and Warranties of Buyer. Buyer represents
and warrants to each Seller as follows:

                  (a) Organization; Authorization. Buyer is a corporation duly
organized, validly existing, and in good standing under the laws of the
jurisdiction of its incorporation. Buyer has full power and authority
(including full corporate power and authority) to execute and deliver this
Agreement and to perform its obligations hereunder. The execution and
performance of this Agreement have been duly authorized by all necessary action
on the part of Buyer, and this Agreement when executed and delivered shall
constitute a valid and legally binding obligation of Buyer, enforceable in
accordance with its terms, except as enforceability may be limited by
bankruptcy, similar laws of debtor relief and general principles of equity.

                  (b) Investment Representations. Buyer is purchasing the
Shares for investment purposes and is not purchasing the Shares with a view to
the public sale or distribution of any part thereof, and Buyer has no present
intention of selling, granting participation in, or otherwise distributing the
Shares in violation of any federal or state securities laws. Buyer has been
given access to all information regarding Allegiance that it has requested from
Sellers. Buyer is capable of evaluating and has evaluated the merits and risks
of its purchase of the Shares and is able to bear the economic risk of its
investment in the Shares. Buyer recognizes that it must bear the economic risk
of the investment represented by its purchase of the Shares for an indefinite
period. Buyer understands that the Shares have not been registered under the
Securities Act of 1933, as amended, on the basis that the sale provided for in
this Agreement is exempt pursuant to Section 4(1) of that Act and that the
reliance of Sellers on such exemptions is predicated upon Buyer's
representations set forth herein.



                                      -5-

Purchase Agreement Final
<PAGE>   7

                  (c) Conflicts. The execution, delivery and performance of
this Agreement by Buyer does not conflict with, violate or result in the breach
of, or create any lien or encumbrance on the assets of Buyer pursuant to, any
agreement, instrument, order, judgment, decree, law or governmental regulation
to which Buyer is a party or is subject.

                  (d) Brokers' Fees. Buyer has no liability or obligation to
pay any fees or commissions to any broker, finder, or agent with respect to the
transactions contemplated by this Agreement for which any Seller or any other
party could become liable or otherwise obligated.

                  (e) No Trading. Neither Buyer nor any of it affiliates has
directly or indirectly traded in the Common Stock or any derivative thereof
during the fifteen days prior to the date of this Agreement.

                  9. No Transfer of Existing Rights and Obligations. Sellers
are parties to various agreements that under certain circumstances give the
Common Stock transferees of Sellers certain rights and subjects such
transferees to certain obligations. Notwithstanding any such agreements, Buyer
shall not, by virtue of its acquisition of Common Stock hereunder, acquire any
such contractual rights or become subject to any such contractual obligations,
it being the intent of the parties that Buyer shall acquire rights and
obligations that are applicable to holders of Common Stock generally (such as
pursuant to the Allegiance Amended and Restated Certificate of Incorporation
and Amended and Restated By-Laws or pursuant to applicable law) or that are
specifically granted to Buyer under this Agreement or the agreements being
entered into in connection herewith or entered into after the date hereof.

                  10. Share Transfers During Option Period. During the Option
Period, neither Buyer, Sellers (not including any holders of Management
Shares), nor any of their respective affiliates shall directly or indirectly
purchase, sell or otherwise transfer any shares of Common Stock or any options,
rights or derivative securities relating to Common Stock other than pursuant to
this Agreement. General partners or managing members (or Persons holding
similar positions) of any Seller who are not otherwise affiliates of
Allegiance, limited partners and non-managing members of any Sellers shall not
be considered to be affiliates of a Seller. Notwithstanding the foregoing, each
Seller shall have the right during the Option Period to distribute to such
Seller's partners or members shares of Common Stock so long as such Seller
retains at least a number of shares of Common Stock equal to such Seller's
Option Shares. In connection with any such distribution, the Seller making the
distribution shall retain a single investment banker to assist in such
distribution and in the sale of any shares distributed pursuant thereto. Such
Seller shall use its reasonable best efforts to have such investment banking
firm facilitate sales by investors who receive such shares of Common Stock upon
such distribution, to Buyer in the event any such investors desire to sell and
Buyer desires to purchase such shares. The purchase price in any such
transaction shall be determined by Buyer and the seller of any such shares. The
sale of shares to Buyer in this manner shall not reduce the number of Option
Shares hereunder.



                                      -6-

Purchase Agreement Final
<PAGE>   8

                  11. Termination. This Agreement may be terminated at any time
prior to the Initial Closing:

                  (a) by mutual agreement of Buyer and Sellers; and

                  (b) by any party hereto if the Initial Closing has not
occurred by September 30, 1999, unless extended by mutual agreement or unless
failure to consummate the Initial Closing is attributable to a failure on the
party seeking to terminate this Agreement to perform any material obligation
required to be performed by such party at or prior to the Initial Closing.

                  12. Amendments and Waivers. No amendment of any provision of
this Agreement shall be valid unless the same shall be in writing and signed by
each party hereto. No waiver by any party of any default, misrepresentation, or
breach of warranty or covenant hereunder, whether intentional or not, shall be
deemed to extend to any prior or subsequent default, misrepresentation, or
breach of warranty or covenant hereunder or affect in any way any rights
arising by virtue of any prior or subsequent such occurrence.

                  13. Complete Agreement. This Agreement including the Exhibits
attached hereto embody the complete agreement and understanding among the
parties hereto with respect to the subject matter hereof and supersedes and
preempts any prior understandings, agreements or representations by or among
the parties, written or oral, which may have related to the subject matter
hereof in any way.

                  14. Expenses. Buyer, each of the Sellers and Allegiance shall
each bear its own costs and expenses (including, without limitation, legal fees
and expenses and applicable Hart-Scott-Rodino filing fees) incurred in
connection with, or arising out of, this Agreement and the transactions
contemplated hereby.

                  15. Counterparts. This Agreement may be executed in two or
more counterparts (including by means of telecopied signature pages), each of
which shall be deemed to be an original, but all of which taken together shall
constitute one and the same agreement.

                  16. Further Assurances. After the Closing, as and when
requested by Buyer, Sellers shall, without further consideration, execute and
deliver all such instruments of conveyance and transfer and shall take such
further actions as Buyer may deem reasonably necessary or desirable in order to
transfer the Shares to Buyer and to carry out fully the provisions and purposes
of this Agreement.

                  17. No Transfer of Rights; Successors and Assigns. Buyer may
not assign either this Agreement or any of its rights, interests, or
obligations hereunder without the prior written approval of each of the
Sellers. This Agreement is intended to bind and inure to the benefit of and be
enforceable by the parties hereto and their respective successors and permitted
assigns.



                                      -7-

Purchase Agreement Final
<PAGE>   9

                  18. GOVERNING LAW. THE CORPORATE LAW OF THE STATE OF DELAWARE
SHALL GOVERN ALL ISSUES AND QUESTIONS CONCERNING THE RELATIVE RIGHTS OF
ALLEGIANCE AND ITS STOCKHOLDERS. ALL OTHER 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 ILLINOIS, WITHOUT GIVING EFFECT TO
ANY CHOICE OF LAW OR CONFLICT OF LAW RULES OR PROVISIONS (WHETHER OF THE STATE
OF ILLINOIS OR ANY OTHER JURISDICTION) THAT WOULD CAUSE THE APPLICATION OF THE
LAWS OF ANY JURISDICTION OTHER THAN THE STATE OF ILLINOIS.

                  19. Headings. The section headings contained in this
Agreement are inserted for convenience only and shall not affect in any way the
meaning or interpretation of this Agreement.

                  20. Notice. 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 communications shall be sent
to the parties hereto at the address set forth below, 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.

                  If to Allegiance

                  1950 N. Stemmons Freeway, Suite 3026
                  Dallas, Texas 75207
                  Attention: Royce J. Holland, Chairman and CEO
                  Telephone: (214) 261-7100
                  Facsimile: (214) 261-7107

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

                  Mark B. Tresnowski
                  Senior Vice President and General Counsel
                  4 Westbrook Corporate Center
                  Suite 400
                  Westchester, IL 60154
                  Telephone: (708) 836-5240
                  Facsimile: (708) 836-5250



                                      -8-

Purchase Agreement Final
<PAGE>   10

                  If to Sellers:

                  Madison Dearborn Capital Partners II, L.P.
                  Three First National Plaza
                  Suite 300
                  Chicago, IL 60602
                  Attention: James N. Perry, Jr.
                  Telephone: (312) 895-1000
                  Telecopy: (312) 895-1001

                  Frontenac Company
                  135 S. LaSalle Street
                  Chicago, IL 60603
                  Attention: James Crawford III
                  Telephone: (312) 368-0044
                  Telecopy: (312) 368-9520

                  Battery Venture Partners
                  20 William Street
                  Wellesley, MA 02181
                  Attention: Richard Frisbie
                  Telephone:  (781) 237-1001
                  Telecopy: (781) 237-7788

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

                  Edward T. Swan
                  Jeffrey W. Richards
                  Kirkland & Ellis
                  200 East Randolph Drive
                  Chicago, IL 60601
                  Telephone: (312) 861-2456
                             (312) 861-2473
                  Telecopy: (312) 861-2200

                  If to Buyer:

                  Vulcan Ventures Incorporated
                  110 110th Avenue NE, Suite 550
                  Bellevue, WA 98004
                  Attention: Dino Vendetti
                  Telephone: (425) 453-2338
                  Telecopy: (425) 453-1985



                                      -9-

Purchase Agreement Final
<PAGE>   11

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

                  Christopher W. Wright
                  Cooley Godward LLP
                  5200 Carillon Point
                  Kirkland, Washington 98033-7355
                  Telephone: (425) 893-7700
                  Telecopy: (425) 893-7777

                  21. Press Release and Announcements. All press releases and
other public announcements relating to the transactions contemplated hereby
(including with respect to any termination of this Agreement) shall be prepared
jointly by Allegiance, Buyer and Sellers and shall be made at such time and in
such manner and forum as shall be mutually agreed to by the parties.
Notwithstanding anything herein to the contrary, at any time after the date
hereof, Allegiance may file with the Securities and Exchange Commission a
Current Report on Form 8-K with respect to this Agreement and may file a copy
of this Agreement and any related agreement as an exhibit to such report.

                  22. 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.

                  23. Allocation of Initial Aggregate Price. The parties hereto
agree that all of the Initial Aggregate Price shall be allocated to the Initial
Closing Shares and that no part of the Initial Aggregate Price shall be
allocated to the Option. Each of the parties hereto agrees that it will
allocate the Initial Aggregate Price for tax and/or accounting purposes
consistent with the terms hereof.


                                  *  *  *  *




                                     -10-

Purchase Agreement Final
<PAGE>   12

                  IN WITNESS WHEREOF, the parties have duly executed this
Common Stock Purchase and Option Agreement on the day and year first above
written.


                            ALLEGIANCE:

                            Allegiance Telecom, Inc.

                            By  /s/ ROYCE J. HOLLAND
                               -------------------------------------

                            Name    Royce J. Holland
                                 -----------------------------------

                            Its     Chairman and CEO
                                ------------------------------------


                            BUYER:

                            Vulcan Ventures Incorporated

                            By  /s/ WILLIAM D. SAVOY
                               -------------------------------------

                            Name    William D. Savoy
                                 -----------------------------------

                            Its     Vice President
                                ------------------------------------


                            SELLERS:

                            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/ GARY J. LITTLE
                               -------------------------------------

                            Name    Gary J. Little
                                 -----------------------------------

                            Its     CFO
                                ------------------------------------




                                     -11-

Purchase Agreement Final
<PAGE>   13

                            FRONTENAC VII LIMITED PARTNERSHIP
                            By: Frontenac Company VII, LLC, its general partner

                            By  /s/ JAMES E. CRAWFORD III
                               -------------------------------------

                            Name    James E. Crawford III
                                 -----------------------------------

                            Its     Member
                                ------------------------------------


                            FRONTENAC MASTERS VII LIMITED PARTNERSHIP
                            By: Frontenac Company VII, LLC, its general partner

                            By  /s/ JAMES E. CRAWFORD III
                               -------------------------------------

                            Name    James E. Crawford III
                                 -----------------------------------

                            Its     Member
                                ------------------------------------


                            BATTERY VENTURES IV, L.P.
                            By: Battery Partners IV, L.P., its general partner

                            By  /s/ RICHARD FRISBIE
                               -------------------------------------

                            Name    Richard Frisbie
                                 -----------------------------------

                            Its     Member Manager
                                ------------------------------------


                            BATTERY INVESTMENT PARTNERS IV, LLC

                            By  /s/ RICHARD FRISBIE
                               -------------------------------------

                            Name    Richard Frisbie
                                 -----------------------------------

                            Its     Member Manager
                                ------------------------------------




                                     -12-


Purchase Agreement Final
<PAGE>   14

                                   SCHEDULE I


<TABLE>
<CAPTION>
- ------------------------------------------------------------------------------------------------------------------------
SELLERS                                                               SHARES OWNED          INITIAL        OPTION SHARES
                                                                     AUGUST 3, 1999         CLOSING
                                                                                            SHARES
- ------------------------------------------------------------------------------------------------------------------------
<S>                                                                  <C>                   <C>             <C>
Madison Dearborn Capital Partners II, L.P.                               8,302,247           899,372         2,486,464
                                                                        ----------         ---------         ---------

Frontenac VII Limited Partnership                                        3,250,475           352,120           973,494
                                                                        ----------         ---------         ---------

Frontenac Masters VII Limited Partnership                                  162,524            17,606            48,675
                                                                        ----------         ---------         ---------

Battery Ventures IV, L.P.                                                2,099,527           227,439           628,793
                                                                        ----------         ---------         ---------

Battery Investment Partners IV, LLC                                         31,972             3,463             9,575
                                                                        ----------         ---------         ---------

Management, with respect to the Option Closing only                                                            852,999
                                                                        ----------         ---------         ---------
                            Total                                       13,846,745         1,500,000         5,000,000

- ------------------------------------------------------------------------------------------------------------------------
</TABLE>

<PAGE>   1
                                                                    EXHIBIT 99.2


                              COUNTERPART AGREEMENT


         THIS COUNTERPART AGREEMENT (this "Agreement") is made as of September
13, 1999, by and among the parties listed on the signature pages hereto
(collectively, the "Sellers"), Reed E. Hundt ("Hundt") and Gregory E. Lawler
("Lawler").

         WHEREAS, the Sellers, Vulcan Ventures Incorporated ("Buyer") and
Allegiance Telecom, Inc. ("Allegiance") have entered into that certain Common
Stock Purchase and Option Agreement dated as of August 3, 1999, a copy of which
is attached hereto as Exhibit A (the "Purchase Agreement"). Pursuant to the
Purchase Agreement, at the Initial Closing, the Sellers intend to sell and Buyer
intends to purchase, an aggregate of 1,500,000 shares of the common stock of
Allegiance (the "Shares"). Capitalized terms used but not otherwise defined
herein have the meanings given to such terms in the Purchase Agreement.

         WHEREAS, the Sellers wish to assign to Hundt and Lawler, their right to
sell to Buyer, that number of Shares as set forth herein.

         WHEREAS, the parties hereto desire that each of Hundt and Lawler become
a party to the Purchase Agreement as set forth herein.

         NOW, THEREFORE, in consideration of the premises and the mutual
promises herein made, and in consideration of the covenants herein contained,
the parties hereto agree as follows:

1. Addition of Hundt and Lawler to the Purchase Agreement. The parties hereto
agree that, by and upon execution of this Agreement, each of Hundt and Lawler
shall as of the date hereof, (a) be a party to the Purchase Agreement and shall
for all purposes be considered a "Seller" thereunder (including, but not limited
to, making the representations and warranties set forth in Section 7 of the
Purchase Agreement, as of the date hereof) and (b) be entitled to all of the
rights and benefits and subject to all of the duties and obligations of a Seller
thereunder, as fully as if Hundt and Lawler were an original signatory thereto
in such capacities. Notwithstanding anything herein to the contrary, neither
Hundt nor Lawler shall have any right to participate in the sale of any Option
Shares.

2. Number of Shares to be Sold. The Sellers hereby assign to: (a) Hundt, the
right to sell an aggregate of 15,000 Shares and (b) Lawler, the right to sell an
aggregate of 10,000 Shares. The number of Shares to be sold to Buyer at the
Initial Closing by each of the Sellers, Hundt and Lawler is set forth on
Schedule I hereto.

3. Continuing Effect. This Agreement shall not constitute an amendment or waiver
of any provision of the Purchase Agreement, which shall continue and remain in
full force and effect in accordance with its terms.

4. Amendments. No amendment, modification or waiver of any provision of this
Agreement shall be valid unless the same shall be in writing and signed by each
party hereto.


                                      - 1 -

COUNTERPART AGREEMENT Final
<PAGE>   2

5. Complete Agreement. This Agreement including Exhibit A and Schedule I
attached hereto embody the complete agreement and understanding among the
parties hereto with respect to the subject matter hereof and supersedes and
preempts any prior understandings, agreements or representations by or among the
parties, written or oral, which may have related to the subject matter hereof in
any way.

6. Counterparts. This Agreement may be executed in two or more counterparts
(including by means of telecopied signature pages), each of which shall be
deemed to be an original, but all of which taken together shall constitute one
and the same agreement.

7. Assignment. Neither Hundt nor Lawler may assign either this Agreement or any
of its rights, interests, or obligations hereunder without the prior written
approval of each of the Sellers. This Agreement is intended to bind and inure to
the benefit of and be enforceable by the parties hereto and their respective
successors and permitted assigns.

8. GOVERNING LAW. THE CORPORATE LAW OF THE STATE OF DELAWARE SHALL GOVERN ALL
ISSUES AND QUESTIONS CONCERNING THE RELATIVE RIGHTS OF ALLEGIANCE AND ITS
STOCKHOLDERS. ALL OTHER 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 ILLINOIS, WITHOUT GIVING EFFECT TO ANY CHOICE OF LAW OR
CONFLICT OF LAW RULES OR PROVISIONS (WHETHER OF THE STATE OF ILLINOIS OR ANY
OTHER JURISDICTION) THAT WOULD CAUSE THE APPLICATION OF THE LAWS OF ANY
JURISDICTION OTHER THAN THE STATE OF ILLINOIS.

9. Headings. The section headings contained in this Agreement are inserted for
convenience only and shall not affect in any way the meaning or interpretation
of this Agreement.

10. 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.


                                    * * * * *


                                      - 2 -


COUNTERPART AGREEMENT Final
<PAGE>   3




         IN WITNESS WHEREOF, the parties hereto have executed this Counterpart
Agreement as of the date first above written.

                                       /s/ REED E. HUNDT
                                       -----------------------------------------
                                       REED E. HUNDT

                                       /s/ GREGORY E. LAWLER
                                       -----------------------------------------
                                       GREGORY E. LAWLER


                                       SELLERS:

                                       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/ GARY J. LITTLE
                                          --------------------------------------

                                       Name: Gary J. Little
                                            ------------------------------------

                                       Its: Chief Financial Officer
                                           -------------------------------------


                                       FRONTENAC VII LIMITED PARTNERSHIP
                                       By: Frontenac Company VII, LLC, its
                                           general partner

                                       By: /s/ JAMES E. CRAWFORD III
                                          --------------------------------------

                                       Name: James E. Crawford III
                                            ------------------------------------

                                       Its: Member
                                           -------------------------------------


                                       FRONTENAC MASTERS VII LIMITED PARTNERSHIP
                                       By: Frontenac Company VII, LLC, its
                                           general partner

                                       By: /s/ JAMES E. CRAWFORD III
                                          --------------------------------------

                                       Name: James E. Crawford III
                                            ------------------------------------

                                       Its: Member
                                           -------------------------------------


                                      - 3 -

COUNTERPART AGREEMENT Final
<PAGE>   4




                                       BATTERY VENTURES IV, L.P.
                                       By: Battery Partners IV, L.P., its
                                           general partner

                                       By: /s/ RICHARD FRISBIE
                                          --------------------------------------

                                       Name: Richard Frisbie
                                            ------------------------------------

                                       Its: Member Manager
                                           -------------------------------------


                                       BATTERY INVESTMENT PARTNERS IV, LLC

                                       By: /s/ RICHARD FRISBIE
                                          --------------------------------------

                                       Name: Richard Frisbie
                                            ------------------------------------

                                       Its: Member Manager
                                           -------------------------------------






                                      - 4 -

COUNTERPART AGREEMENT Final
<PAGE>   5



                                   SCHEDULE I

<TABLE>
<CAPTION>

                                                          SHARES TO BE SOLD AT THE
STOCKHOLDER                                                    INITIAL CLOSING
- --------------------------------------------------------  ------------------------
<S>                                                       <C>
Madison Dearborn Capital Partners II, L.P.                        884,382
Frontenac VII Limited Partnership                                 346,251
Frontenac Masters VII Limited Partnership                          17,313
Battery Ventures IV, L.P.                                         223,648
Battery Investment Partners IV, LLC                                 3,406
Reed Hundt                                                         15,000
Greg Lawler                                                        10,000
                                                          ------------------------
TOTAL                                                           1,500,000
</TABLE>






                                      - 5 -
COUNTERPART AGREEMENT Final

<PAGE>   1

                                                                    EXHIBIT 99.3

                               INVESTORS AGREEMENT


                  THIS INVESTORS AGREEMENT (this "AGREEMENT") is made as of
September 13, 1999, between Allegiance Telecom, Inc., a Delaware corporation
(the "COMPANY") and Vulcan Ventures Incorporated, a Washington corporation
("INVESTOR"). Capitalized terms used herein are defined in paragraph 7 hereof.

                  Investor has agreed to purchase shares of the Company's Common
Stock pursuant to a Common Stock Purchase and Option Agreement among Investor,
the Company, Madison Dearborn Capital Partners II, L.P., Frontenac VII Limited
Partnership, Frontenac Masters VII Limited Partnership, Battery Venture Partners
IV, L.P. and Battery Investment Partners IV, LLC, dated as of August 3, 1999
(the "PURCHASE AGREEMENT"). Investor also has the option to purchase additional
shares of the Company's Common Stock pursuant to the Purchase Agreement. The
execution and delivery of this Agreement is a condition to the closing of the
transactions pursuant to the Purchase Agreement. Capitalized terms used herein
which are defined in the Purchase Agreement shall have the meanings assigned in
the Purchase Agreement unless otherwise defined herein.

                  In consideration of the mutual covenants contained herein and
other good and valuable consideration, the receipt and sufficiency of which are
hereby acknowledged, the parties to this Agreement agree as follows:

                  1. Board of Directors.

                  (a) Investor Directors. From and after the Initial Closing and
until the provisions of this paragraph 1 cease to apply, the Company shall use
its best efforts to cause to be elected one board designee nominated by Investor
(an "INVESTOR DIRECTOR") so long as Investor holds at least 1,200,000 shares of
Common Stock (as such number is adjusted after the date hereof to take into
account any stock dividends, stock splits and other recapitalizations) and shall
use such efforts to cause to be elected a second Investor Director so long as
Investor has exercised the Option for at least 2,500,000 shares of Common Stock
and continues to hold at least 4,000,000 shares of Common Stock (as such number
in each case is adjusted after the date hereof to take into account any stock
dividends, stock splits and other recapitalizations). No Investor Director,
however, may be an employee or officer of the Company or its Subsidiaries. If
Investor fails at any time to advise the Board in writing of its Board designees
for the Company's next annual stockholders' meeting or any extraordinary meeting
in lieu thereof, then the Investor designees for any such annual meeting or
extraordinary meeting shall be deemed to be the incumbent Investor Directors. If
Investor at any time falls below the thresholds necessary to maintain one or
more Investor Directors, Investor shall lose the right to nominate candidates
for the directorships held by such Investor Directors at all future elections of
the Board.

                  (b) Actions at the Initial Closing and the Option Closing. The
Company shall take, or cause to be taken, such action as may be necessary or
advisable to ensure that simultaneously


Investors Agreement Final
                                       -1-
<PAGE>   2


with the Initial Closing, the Board shall have at least one vacancy (which may
be created by increasing the number of directorships or by accepting the
resignation of an existing director) which shall be vacant pending designation
by Investor of one individual to serve as a member of the Board pursuant to this
Agreement. The Company shall take, or cause to be taken, such action as may be
necessary or advisable to ensure that simultaneously with the Initial Closing,
each of the committees of the Board of Directors shall include one director
designated by Investor. If the Option is exercised for at least 2,500,000 shares
(as such number is adjusted after the date hereof to take into account any stock
dividends, stock splits and other recapitalizations), the Company shall take,
or cause to be taken, such action as may be necessary or advisable to ensure
that simultaneously with the Option Closing, the Board shall have at least one
vacancy (which may be created by increasing the number of directorships or by
accepting the resignation of an existing director) which shall be vacant pending
designation by Investor of one additional individual to serve as a member of the
Board pursuant to this Agreement.

                  (c) Expenses. The Company shall pay the reasonable
out-of-pocket expenses incurred by each Investor Director in connection with
attending the meetings of the Board and any committee thereof. So long as any
Investor Director designated under this Agreement serves on the Board and for
five years thereafter, the Company shall maintain directors and officers
indemnity insurance coverage satisfactory to the Board at the time such
insurance is first obtained and not thereafter reduced in amount or coverage,
and the Company's certificate of incorporation and bylaws shall provide for
indemnification and exculpation of directors to the fullest extent permitted
under applicable law.

                  (d) Termination. The rights and requirements under this
paragraph 1 with respect to any Investor Director shall terminate upon the
earlier of (i) the time that Investor fails to hold in the aggregate the shares
necessary to designate such Investor Director pursuant to this paragraph 1 (and
such right shall not be reinstated) and (ii) the closing of a Sale of the
Company.

                  2. Representations and Warranties. Investor represents and
warrants that (i) this Agreement has been duly authorized, executed and
delivered by Investor and constitutes the valid and binding obligation of
Investor, enforceable in accordance with its terms, except as enforceability may
be limited by bankruptcy, similar laws of debtor relief and general principles
of equity and (ii) Investor has not granted and is not a party to any proxy,
voting trust or other agreement which is inconsistent with, conflicts with or
violates any provision of this Agreement. No holder of Investor Shares shall
grant any proxy or become party to any voting trust or other agreement which is
inconsistent with, conflicts with or violates any provision of this Agreement.

                  3. Standstill.

                  (a) Except with the prior approval of the Board (as evidenced
by a duly adopted resolution), during the Standstill Period, Investor will not,
and each holder of Investor Shares will not, and each of the Investor and holder
of Investor Shares will not cause or permit its Affiliates or Associates to,
directly or indirectly:


Investors Agreement Final

                                      -2-
<PAGE>   3

                   (i)   make, effect, initiate, propose, cause or participate
                         in (including, but not limited to, arranging any
                         financing for, or provide any financing commitment
                         for):

                         (A) any acquisition of ownership (including, but not
                             limited to, beneficial ownership as defined in Rule
                             13d-3 under the Securities Exchange Act) of any
                             Voting Securities or securities convertible or
                             exchangeable into or exercisable for any Voting
                             Securities of the Company or any Subsidiary or
                             other Affiliate of the Company,

                         (B) any acquisition of any assets of the Company or any
                             Subsidiary or other Affiliate of the Company, or

                         (C) any tender offer, exchange offer, merger, business
                             combination, recapitalization, restructuring,
                             liquidation, dissolution or extraordinary
                             transaction involving the Company or any Subsidiary
                             or other Affiliate of the Company, or involving any
                             securities or assets of the Company or any
                             Subsidiary or other Affiliate of the Company;

                         provided, that the Investor may take any of the
                         above-described actions within 60 days after another
                         Person that is not an Affiliate or Associate of
                         Investor has made a publicly announced proposal to take
                         any such action that would result in a Sale of the
                         Company so long as such Investor's actions are not in
                         concert with such other Person.

                   (ii)  become a member of a group with respect to the Common
                         Stock, other equity securities or assets of the
                         Company;

                   (iii) call or seek to call any special meeting of the
                         Company's stockholders for any reason whatsoever or
                         initiate a stockholder vote or action by written
                         consent of the Company's stockholders with respect to
                         any matter;

                   (iv)  initiate, propose, make or in any way participate in,
                         directly or indirectly, any "solicitation" of "proxies"
                         to vote, or seek to influence any person or entity with
                         respect to the Company in opposition to any matter
                         which has been recommended by the Board or in favor of
                         any matter which has not been approved by the Board; or

                   (v)   enter into any discussions, negotiations, arrangements
                         or understandings with any third party with respect to
                         any of the foregoing.


Investors Agreement Final

                                      -3-
<PAGE>   4

                  (b) Notwithstanding paragraph 3(a)(i) above, Investor and its
Affiliates and Associates may acquire Common Stock from and after the Closing to
the extent that such acquisition, which when combined with the shares of Common
Stock then owned by Investor and its Affiliates and Associates, would not result
in Investor and its Affiliates and Associates beneficially owning more than an
aggregate of 20% of the then outstanding Voting Securities of the Company.

                  (c) Each holder of Investor Shares agrees that, in the event
of any breach of the provisions of this paragraph 3, the Company shall in
addition to any right at law to damages be deemed irreparably harmed and
entitled to equitable relief (without the posting of any bond or other
security), including injunction requiring prompt disposition of securities
acquired contrary to this Agreement in a manner which is calculated to cause
wide distribution of the shares and which is agreeable to the Company.

                  (d) In the event that the Company shall adopt a stockholder
rights plan with provisions that are triggered by the acquisition of beneficial
ownership of a specified percentage of the Common Stock (a "TRIGGER
PERCENTAGE"), the Company agrees that, for purposes of determining application
of the stockholder rights plan to Investor, the plan will provide for a 20%
Trigger Percentage even if the general Trigger Percentage is below 20%.

                  4. Restrictions on Transfers of Investor Shares.

                  (a) No Transfers. Investor acknowledges that the Investor
Shares have not been registered under the Securities Act by reason of a specific
exemption therefrom, and may not be Transferred except in compliance with the
Securities Act. Until the first anniversary of the date of this Agreement, no
holder of Investor Shares shall Transfer any Investor Shares beneficially owned
by such Person on the date hereof or hereafter acquired, without the prior
approval of the Board (as evidenced by a duly adopted resolution); provided that
nothing contained in this paragraph 4 shall prohibit any holder of Investor
Shares from pledging such shares; and provided further that the provisions of
this paragraph 4(a) shall terminate and cease to be effective upon and with
respect to the consummation of a Sale of the Company. Thereafter, subject to
paragraph 4(c) below, Investor Shares are transferable only pursuant to (i)
public offerings registered under the Securities Act, (ii) Rule 144 or Rule 144A
of the Securities and Exchange Commission (or any similar rule or rules then in
force) if such rule is available, and (iii) any other legally available means of
transfer.

                  (b) Permitted Transfers. The restrictions set forth in this
paragraph 4 shall not apply with respect to any Transfer of Investor Shares by
Investor and its Affiliates to and among each other; provided that the
restrictions contained in this paragraph 4 shall continue to be applicable to
the Investor Shares after any such Transfer and provided further that the
transferees of such Investor Shares shall have agreed in writing to be bound by
the provisions of this Agreement affecting the Investor Shares so transferred.
Notwithstanding the foregoing, no party shall avoid the provisions of this
Agreement by making one or more transfers to one or more Affiliates and then
disposing of all or any portion of such party's interest in any such Affiliates.


Investors Agreement Final

                                      -4-
<PAGE>   5

                  (c) Opinion Delivery. In connection with the transfer of
Investor Shares (other than a transfer described in paragraphs 4(a)(i) or
4(a)(ii) above), the holder thereof shall deliver written notice to the Company
describing in reasonable detail the transfer or proposed transfer, together with
an opinion of counsel which (to the Company's reasonable satisfaction) is
knowledgeable in securities law matters to the effect that such transfer of
Investor Shares may be effected without registration of such shares under the
Securities Act. In addition, if the holder of the Investor Shares delivers to
the Company an opinion of counsel that no subsequent transfer of such shares
shall require registration under the Securities Act, the Company shall promptly
upon such contemplated transfer deliver new certificates for such shares which
do not bear the Securities Act legend set forth in paragraph 5 below. If the
Company is not required to deliver new certificates for such Investor Shares not
bearing such legend, the holder thereof shall not transfer the same until the
prospective transferee has confirmed to the Company in writing its agreement to
be bound by the conditions contained in this paragraph 4 and paragraphs 5 or 6
below.

                  5. Legend. Each certificate evidencing Investor Shares and
each certificate issued in exchange for or upon the transfer of any Investor
Shares (if such shares remain Investor Shares after such transfer) shall be
stamped or otherwise imprinted with a legend in substantially the following
form:

                  "THE SECURITIES REPRESENTED BY THIS CERTIFICATE WERE
                  ORIGINALLY ISSUED ON _____________________, 1999, AND HAVE NOT
                  BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933, AS AMENDED
                  (THE "SECURITIES ACT"), OR THE SECURITIES LAWS OF ANY STATE.
                  SUCH SECURITIES MAY NOT BE OFFERED, SOLD, TRANSFERRED OR
                  OTHERWISE DISPOSED OF EXCEPT PURSUANT TO AN EFFECTIVE
                  REGISTRATION STATEMENT OR PURSUANT TO AN EXEMPTION FROM, OR IN
                  A TRANSACTION NOT SUBJECT TO, THE REGISTRATION REQUIREMENTS OF
                  THE SECURITIES ACT AND APPLICABLE STATE SECURITIES LAWS.

                  THE SECURITIES REPRESENTED BY THIS CERTIFICATE ARE SUBJECT TO
                  RESTRICTIONS ON TRANSFER AND RESALE AND OTHER PROVISIONS UNDER
                  AN INVESTORS AGREEMENT DATED AS OF _____________, 1999 BETWEEN
                  THE ISSUER OF SUCH SECURITIES (THE "COMPANY") AND THE INITIAL
                  HOLDER OF THESE SECURITIES, AS SUCH AGREEMENT MAY BE AMENDED
                  AND MODIFIED FROM TIME TO TIME. THE COMPANY RESERVES THE RIGHT
                  TO REFUSE THE TRANSFER OF SUCH SECURITIES UNTIL SUCH
                  CONDITIONS HAVE BEEN FULFILLED WITH RESPECT TO SUCH TRANSFER.
                  A COPY OF SUCH INVESTORS AGREEMENT SHALL BE FURNISHED WITHOUT
                  CHARGE BY THE COMPANY TO THE HOLDER HEREOF UPON WRITTEN
                  REQUEST."

Investors Agreement Final

                                      -5-
<PAGE>   6

                  The legends set forth above shall be removed from the
certificates evidencing any shares that cease to be Investor Shares in
accordance with the definition of "Investor Shares."

                  6. Transfer. Prior to transferring any Investor Shares (other
than a Sale of the Company) to any Person, the holders of Investor Shares shall
cause the prospective transferee to be bound by this Agreement and to execute
and deliver to the Company and the holders of Investor Shares a counterpart of
this Agreement. Any Transfer or attempted Transfer of any Investor Shares in
violation of any provision of this Agreement shall be void, and the Company
shall not record such Transfer on its books or treat any purported transferee of
such Investor Shares as the owner of such shares for any purpose.

                  7. Definitions.

                  "Associate" has the meaning given to such term in Rule 12b-2
of the Securities Exchange Act.

                  "Affiliate" means, with respect to any Person, any other
Person who, directly or indirectly through one or more intermediaries, controls,
is controlled by or is under common control with such Person. For purposes of
this definition and this Agreement, the term "control" (and correlative terms)
means the power, whether by contract, equity ownership or otherwise, to direct
or cause the direction of management or policies of a Person.

                  "Agreement" has the meaning set forth in the preamble.

                  "beneficial ownership" (including the term "beneficially
owning" and other correlative terms) has the meaning given to such terms in
Section 13(d)(3) of the Securities Exchange Act.

                  "Board" means the Board of Directors of the Company as from
time to time hereafter constituted.

                  "Common Stock" means the Company's common stock, par value
$.01 per share, and any shares of capital stock for or into which such Common
stock hereafter is exchanged, converted, reclassified or recapitalized by the
Company or pursuant to an agreement to which the Company is a party.

                  "Company" has the meaning set forth in the preamble.

                  "group" has the meaning given to such term in Section 13(d)(3)
of the Securities Exchange Act.

                  "Investor" has the meaning set forth in the preamble.


Investors Agreement Final

                                      -6-
<PAGE>   7

                  "Investor Director" has the meaning set forth in paragraph
1(a) hereof.

                  "Investor Shares" means (i) any Common Stock purchased
pursuant to the Purchase Agreement or otherwise during the Option Period (or
pursuant to an agreement entered into during the Option Period), (ii) any
capital stock or other equity securities issued or issuable directly or
indirectly with respect to the Common Stock referred to in clause (i) above by
way of stock dividend or stock split or in connection with a combination of
shares, recapitalization, merger, consolidation or other reorganization. As to
any particular shares constituting Investor Shares, such shares shall cease to
be Investor Shares when they have been (x) effectively registered under the
Securities Act and disposed of in accordance with the registration statement
covering them or (y) sold to the public through a broker, dealer or market maker
pursuant to Rule 144 (or any similar provision then in force) under the
Securities Act.

                  "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.

                  "Purchase Agreement" has the meaning set forth in the
preamble.

                  "Sale of the Company" means either (i) the sale, lease,
conveyance or other disposition, in one or a series of related transactions, of
all or substantially all of the assets of the Company and its Subsidiaries,
taken as a whole, or (ii) a transaction or series of transactions (including by
way of merger, consolidation, or sale of stock) the result of which is that the
holders of the Company's outstanding voting stock immediately prior to such
transaction are after giving effect to such transaction no longer, in the
aggregate, the beneficial owners, directly or indirectly through one or more
intermediaries, of more than 50% of the voting power of the outstanding voting
stock of the Company.

                  "Securities Act" means the Securities Act of 1933, as amended
from time to time, and the rules and regulations promulgated thereunder.

                  "Securities Exchange Act" means the Securities Exchange Act of
1934, as amended from time to time, and the rules and regulations promulgated
thereunder.

                  "Standstill Period" means the period beginning on the date of
this Agreement and ending upon the first to occur of (i) the closing of a Sale
of the Company or (ii) the date after the third anniversary hereof on which
Investor has not for 180 days had a representative serving on the Board (and has
waived or otherwise lost its rights hereunder to have such a representative).

                  "Subsidiary" means, with respect to any Person, any
corporation, limited liability company, partnership, association or other
business entity of which (i) if a corporation, a majority of the total voting
power of shares of stock entitled (without regard to the occurrence of any
contingency) to vote in the election of directors, managers or trustees thereof
is at the time owned or controlled, directly or indirectly, by that Person or
one or more of the other Subsidiaries of that

Investors Agreement Final

                                      -7-
<PAGE>   8


Person or a combination thereof, or (ii) if a limited liability company,
partnership, association or other business entity, a majority of the limited
liability company, partnership or other similar ownership interest thereof is at
the time owned or controlled, directly or indirectly, by any Person or one or
more Subsidiaries of that Person or a combination thereof. For purposes hereof,
a Person or Persons shall be deemed to have a majority ownership interest in a
limited liability company, partnership, association or other business entity if
such Person or Persons shall be allocated a majority of limited liability
company, partnership, association or other business entity gains or losses or
shall be or control the managing director or general partner of such limited
liability company, partnership, association or other business entity.

                  "Transfer" means any direct or indirect sale, transfer,
assignment, pledge or other disposition of (whether in one or more transactions
or with or without consideration and whether voluntarily or involuntarily or by
operation of law) any interest in Investor Shares.

                  "Voting Securities" means any securities of the Company
entitled to vote generally in the election of the Company's directors.

                  8. Amendment and Waiver. Except as otherwise provided herein,
no modification, amendment or waiver of any provision of this Agreement shall be
effective against the Company or holder of Investor Shares unless such
modification, amendment or waiver is approved in writing by the Company or the
holders of at least 50% of the Investor Shares, respectively. The failure of any
party to enforce any of the provisions of this Agreement shall in no way be
construed as a waiver of such provisions and shall not affect the right of such
party thereafter to enforce each and every provision of this Agreement in
accordance with its terms.

                  9. 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 invalid,
illegal or unenforceable in any respect under any applicable law or rule in any
jurisdiction, such invalidity, illegality or unenforceability shall not affect
the validity, legality or enforceability of any other provision of this
Agreement in such jurisdiction or affect the validity, legality or
enforceability of any provision in any other jurisdiction, but this Agreement
shall be reformed, construed and enforced in such jurisdiction as if such
invalid, illegal or unenforceable provision had never been contained herein.

                  10. Entire Agreement. Except as otherwise expressly set forth
herein, this Agreement embodies the complete agreement and understanding among
the parties hereto with respect to the subject matter hereof and supersedes and
preempts any prior understandings, agreements or representations by or among the
parties, written or oral, which may have related to the subject matter hereof in
any way.

                  11. Successors and Assigns. Except as otherwise provided
herein, this Agreement shall bind and inure to the benefit of and be enforceable
by the Company and its successors and assigns and Investor and any subsequent
holders of Investor Shares and the respective successors and assigns of each of
them, so long as they hold Investor Shares; provided that the rights


Investors Agreement Final

                                      -8-
<PAGE>   9


of Investor under paragraph 1 and under paragraph 3(d) hereof may not be
assigned without the prior written approval of the Company.

                  12. Counterparts. This Agreement may be executed in multiple
counterparts (including by telecopied signature pages), each of which shall be
an original and all of which taken together shall constitute one and the same
agreement.

                  13. Remedies. The Company and Investor shall be entitled to
enforce their rights under this Agreement specifically, to recover damages by
reason of any breach of any provision of this Agreement and to exercise all
other rights existing in their favor. The parties hereto agree and acknowledge
that money damages would not be an adequate remedy for any breach of the
provisions of this Agreement and that the Company and Investor may in its sole
discretion apply to any court of law or equity of competent jurisdiction for
specific performance and/or injunctive relief (without posting a bond or other
security) in order to enforce or prevent any violation of the provisions of this
Agreement.

                  14. 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 communications shall be sent
to the Company at the address set forth below and to any holder of Investor
Shares 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

                  1950 N. Stemmons Freeway, Suite 3026
                  Dallas, Texas 75207
                  Attention: Royce J. Holland, Chairman and CEO
                  Telephone: (214) 261-7100
                  Facsimile: (214) 261-7107

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

                  Mark B. Tresnowski
                  Senior Vice President and General Counsel
                  4 Westbrook Corporate Center
                  Suite 400
                  Westchester, IL 60154
                  Telephone: (708) 836-5240
                  Facsimile: (708) 836-5250

Investors Agreement Final

                                      -9-
<PAGE>   10

                  Investor

                  Vulcan Ventures Incorporated
                  110 110th Avenue NE, Suite 550
                  Bellevue, WA 98004
                  Attention: Dino Vendetti
                  Telephone: (425) 453-2338
                  Telecopy: (425) 453-1985

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

                  Christopher W. Wright
                  Cooley Godward LLP
                  5200 Carillon Point
                  Kirkland, Washington 98033-7355
                  Telephone: (425) 893-7700
                  Telecopy: (425) 893-7777

                  15. GOVERNING LAW. THE CORPORATE LAW OF THE STATE OF DELAWARE
SHALL GOVERN ALL ISSUES AND QUESTIONS CONCERNING THE RELATIVE RIGHTS OF
ALLEGIANCE AND ITS STOCKHOLDERS. ALL OTHER 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 ILLINOIS, WITHOUT GIVING EFFECT TO ANY CHOICE OF
LAW OR CONFLICT OF LAW RULES OR PROVISIONS (WHETHER OF THE STATE OF ILLINOIS OR
ANY OTHER JURISDICTION) THAT WOULD CAUSE THE APPLICATION OF THE LAWS OF ANY
JURISDICTION OTHER THAN THE STATE OF ILLINOIS.

                  16. 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. In the event 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.


Investors Agreement Final

                                      -10-
<PAGE>   11

                  17. 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.

                  18. Expenses. The parties hereto shall each bear their own
costs and expenses (including, without limitation, legal fees and expenses)
incurred in connection with, or arising out of, this Agreement and the
transactions contemplated hereby.

                                     * * * *

Investors Agreement Final

                                      -11-
<PAGE>   12



                  IN WITNESS WHEREOF, the parties hereto have executed this
Investors Agreement on the day and year first above written.


                             ALLEGIANCE TELECOM, INC.

                             By:   /s/ ROYCE J. HOLLAND
                                -------------------------------------------
                             Name: Royce J. Holland
                             Its:  Chairman and Chief Executive Officer


                             VULCAN VENTURES INCORPORATED

                             By:   /s/ WILLIAM D. SAVOY
                                -------------------------------------------

                             Name: William D. Savoy
                                  -----------------------------------------

                             Its:  Vice President
                                 ------------------------------------------

<PAGE>   1
                                                                    EXHIBIT 99.4

                   AMENDED AND RESTATED REGISTRATION AGREEMENT


                  THIS AMENDED AND RESTATED REGISTRATION AGREEMENT (this
"AGREEMENT") is made as of September 13, 1999, by and among Allegiance Telecom,
Inc. ("ALLEGIANCE"), and the stockholders listed on the signature pages hereto.
Capitalized terms used but not otherwise defined herein have the meanings set
forth in paragraph 8 hereof.

                  WHEREAS, Allegiance and the investors listed on Exhibit A
attached hereto are parties to a Registration Agreement dated as of August 13,
1997, as amended on April 9, 1999 (the "REGISTRATION AGREEMENT").

                  WHEREAS, the parties hereto wish to amend and restate the
Registration Agreement in its entirety in connection with the purchase of shares
of Allegiance's common stock by Vulcan Ventures Incorporated ("VULCAN") pursuant
to the Common Stock Purchase and Option Agreement dated as of August 3, 1999
(the "VULCAN PURCHASE AGREEMENT").

                  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 - Original Registrable
Securities. At any time after the date hereof, (i) the holders of a majority of
the Frontenac Registrable Securities then outstanding, the holders of a majority
of the MDCP Registrable Securities then outstanding, and the holders of a
majority of the MSCP Registrable Securities then outstanding may each request up
to two registrations of Registrable Securities on Form S-1 or any similar
long-form registration statement (a "LONG-FORM REGISTRATION"), (ii) the holders
of a majority of the BV Registrable Securities then outstanding and the holders
of a majority of the Management Registrable Securities then outstanding may each
request one Long-Form Registration, and (iii) the holders of at least 5% of the
Original Registrable Securities then outstanding may request registration under
the Securities Act of all or any portion of their Original Registrable
Securities on Form S-3 or any similar short-form registration ("Short-Form
Registration") if available; provided that the aggregate offering value of the
Original Registrable Securities requested to be registered in any registration
under this paragraph 1(a) must be at least $20 million in any Long-Form
Registration, and at least $5 million in any Short-Form Registration.

                  (b) Requests for Registration - Vulcan Registrable Securities.
At any time after September 13, 2000, the holders of a majority of the Vulcan
Registrable Securities then outstanding may request one Long-Form Registration
and up to two Short-Form Registrations; provided that the aggregate offering
value of the Vulcan Registrable Securities requested to be registered in any
registration under this paragraph 1(b) must be at least $5 million in any such
registration.
                  (c) Procedures. All requests for registration under paragraphs
1(a) and 1(b) above are referred to herein as "DEMAND REGISTRATIONS." All
requests for Demand Registrations


                                      -1-


Amended and Restated Registration Agreement Final

<PAGE>   2



shall be made by giving written notice to Allegiance (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, Allegiance shall
give written notice of such requested registration to all other holders of
Registrable Securities and, subject to the provisions of paragraph 1(f) below,
shall include in such registration all Registrable Securities with respect to
which Allegiance has received written requests for inclusion therein within 15
days after the receipt of Allegiance's notice.

                  (d) Expenses; Withdrawal. Allegiance 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 until it has become effective or if the holders of Original
Registrable Securities initially requesting such registration are not able to
register and sell at least 90% of the Original Registrable Securities requested
to be included in such registration; provided that Allegiance 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.
All Long-Form Registrations shall be underwritten registrations unless otherwise
requested by the holders of a majority of the Original Registrable Securities
included in the applicable Long-Form Registration.

                  (e) Short-Form Registrations. Demand Registrations shall be
Short-Form Registrations whenever Allegiance is permitted to use any applicable
short form. After Allegiance has become subject to the reporting requirements of
the Securities Exchange Act, Allegiance 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.

                  (f) Priority on Demand Registrations. Allegiance 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 Allegiance 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, Allegiance shall include in such registration the
number which can be so sold in the following order of priorities:

                      (i) first, the 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 of Registrable Securities owned
                          by each such holder, and

                     (ii) second, other securities requested to be included in
                          such registration.




                                      -2-


Amended and Restated Registration Agreement Final
<PAGE>   3




                  (g) Restrictions on Long-Form Registrations. Allegiance 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 there was no reduction in the number of Registrable
Securities requested to be included. Allegiance may postpone for up to 180 days
the filing or the effectiveness of a registration statement for a Demand
Registration if Allegiance'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 Allegiance or any
of its 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 Allegiance shall pay all Registration Expenses in connection with
such withdrawn registration. Allegiance may delay a Demand Registration
hereunder only once in any twelve-month period.

                  (h) Selection of Underwriters. The Board shall select the
investment banker(s) and manager(s) to administer the offering.

                  (i) Other Registration Rights. Except as provided in this
Agreement, Allegiance shall not grant to any Persons the right to request
Allegiance to register any of its equity securities, 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 total Investor
Registrable Securities and Vulcan Registrable Securities (or, if none,
Registrable Securities) then outstanding; provided that Allegiance 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.

                  2.       PIGGYBACK REGISTRATIONS.

                  (a) Right to Piggyback. Whenever Allegiance 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"), Allegiance
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 include in such registration all
Registrable Securities with respect to which Allegiance has received written
requests for inclusion therein within 20 days after the receipt of Allegiance's
notice.

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


                                      -3-


Amended and Restated Registration Agreement Final
<PAGE>   4




                  (c) Priority on Primary Registrations. If a Piggyback
Registration is an underwritten primary registration on behalf of Allegiance,
and the managing underwriters advise Allegiance 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 Allegiance, Allegiance shall include in such
registration:

                      (i) first, the securities Allegiance proposes to sell,

                     (ii) second, the 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 of Registrable Securities owned
                          by each such holder, and

                    (iii) third, other securities requested to be included in
                          such registration.


                  (d) Priority on Secondary Registrations. If a Piggyback
Registration is an underwritten secondary registration on behalf of holders of
Allegiance's securities, and the managing underwriters advise Allegiance 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, Allegiance 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, the selection of the investment banker(s) and
manager(s) to administer such offering shall be approved by the Board.

                  (f) Other Registrations. If Allegiance 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, Allegiance 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.


                                      -4-

Amended and Restated Registration Agreement Final

<PAGE>   5

                  (g) Piggyback Rights Not Applicable. Notwithstanding anything
herein to the contrary, the piggyback rights set forth in Section 2 of this
Agreement shall not apply to Allegiance's registration of its 12 7/8% senior
notes due 2008, Allegiance's registration of its 11 3/4% senior discount notes
due 2008 nor Allegiance's registration of the exercise of its warrants pursuant
to that certain Warrant Registration Rights Agreement dated as of February 3,
1998.

                  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 Allegiance, or
any securities convertible into or exchangeable or exercisable for such
securities, during the seven days prior to and the 90-day period beginning on
the effective date of any other 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) Allegiance. Allegiance:

                  (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, Form S-4 or any
                      successor form), unless the underwriters managing the
                      registered public offering otherwise agree, and

                  (ii) shall use its reasonable best efforts to cause each
                      holder of 5% or more its Common Stock, or any securities
                      convertible into or exchangeable or exercisable for Common
                      Stock, purchased from Allegiance at any time after the
                      date of 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, Allegiance 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
Allegiance shall as expeditiously as possible:


                                      -5-


Amended and Restated Registration Agreement Final
<PAGE>   6



                  (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, Allegiance 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 Allegiance 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);

                  (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, Allegiance 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 Allegiance 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


                                      -6-

Amended and Restated Registration Agreement Final
<PAGE>   7



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 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 or
a combination of shares);

                  (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 Allegiance, and cause Allegiance'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 Allegiance'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;

                  (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 Allegiance, to participate in the preparation of such
registration or comparable statement and to require the insertion therein of
material, furnished to Allegiance 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, Allegiance shall use its best efforts promptly to obtain the
withdrawal of such order;

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


                                      -7-

Amended and Restated Registration Agreement Final
<PAGE>   8


                  (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 Allegiance'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
Allegiance and all independent certified public accountants, underwriters
(excluding discounts and commissions) and other Persons retained by Allegiance
(all such expenses being herein called "Registration Expenses"), shall be borne
as provided in this Agreement, except that Allegiance 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 Allegiance are
then listed or on the Nasdaq.

                  (b) Reimbursement of Counsel. In connection with each Demand
Registration and each Piggyback Registration, Allegiance shall reimburse the
holders of Registrable Securities included in such registration for the
reasonable fees and disbursements of one counsel chosen by the holders of a
majority of the total Investor Registrable Securities and Vulcan Registrable
Securities (or, if none, Registrable Securities) included in such registration
and for the reasonable fees and disbursements of each additional counsel
retained by any holder of Registrable Securities solely for 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 Allegiance as set forth in paragraph
(b) above) shall be borne and paid by the holders of such Registrable
Securities.

                  6.       INDEMNIFICATION.

                  (a) Allegiance 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 Allegiance by such holder


                                      -8-

Amended and Restated Registration Agreement Final
<PAGE>   9



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 Allegiance has furnished such holder with a sufficient number of copies of
the same. In connection with an underwritten offering, Allegiance 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 Allegiance in writing such information and affidavits as Allegiance
reasonably requests for use in connection with any such registration statement
or prospectus and, to the extent permitted by law, shall indemnify Allegiance,
its directors and officers and each Person who controls Allegiance (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 (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.
Allegiance also agrees to make such provisions, as are reasonably requested by
any indemnified party, for contribution to such party in the event Allegiance'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


                                      -9-

Amended and Restated Registration Agreement Final
<PAGE>   10



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
Allegiance 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 Allegiance 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
Allegiance and its controlling persons in paragraph 6(a) hereof.

                  8.       DEFINITIONS.

                  "BV Registrable Securities" means Registrable Securities held
by Battery Ventures IV, L.P. and Battery Investment Partners IV, LLC or their
respective successors and assigns.

                  "Common Stock" means Allegiance's Common Stock, par value $.01
 per share.

                  "Frontenac Registrable Securities" means Registrable
Securities held by Frontenac VII Limited Partnership and Frontenac Masters VII
Limited Partnership or their respective successors and assigns.

                  "Investor Registrable Securities" means collectively, the BV
Registrable Securities, the Frontenac Registrable Securities, the MDCP
Registrable Securities, and the MSCP Registrable Securities.

                  "Management Registrable Securities" means Registrable
Securities held by the management stockholders listed in Exhibit A hereto.

                  "MDCP Registrable Securities" means Registrable Securities
held by Madison Dearborn Capital Partners II, L.P. or its successor and assigns.

                  "MSCP  Registrable Securities" means Registrable Securities
held by Morgan Stanley Capital Partners III, L.P., MSCP III 892 Investors, L.P.
and Morgan Stanley Capital Investors, L.P. or their respective successors and
assigns.

                  "Original Registrable Securities" means collectively, the
Investor Registrable Securities and the Management Registrable Securities.



                                      -10-

Amended and Restated Registration Agreement Final
<PAGE>   11

                  "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.

                  "Registrable Securities" means (i) any Common Stock issued by
Allegiance to the stockholders listed on Exhibit A hereto pursuant to the Stock
Purchase Agreement dated as of August 13, 1997 by and among Allegiance and the
investor parties thereto or in consideration of any securities purchased
thereunder, or pursuant to an Executive Purchase Agreement between Allegiance
and any employee stockholder of Allegiance or in consideration of any securities
purchased thereunder, or pursuant to the Vulcan Purchase Agreement, as
applicable, (ii) any Common Stock acquired by any Person who holds any Common
Stock described in clause (i) above who was an affiliate of Allegiance at the
time such Person acquired the additional shares of Common Stock sought to be
covered by this clause (ii) and (iii) any Common Stock issued or issuable with
respect to the securities referred to in clauses (i) or (ii) by way of a stock
dividend or stock split or in connection with a combination of shares,
recapitalization, merger, consolidation or other reorganization; provided that
with respect to any Registrable Securities, such securities shall cease to be
Registrable Securities when they have been distributed to the public pursuant to
an offering registered under the Securities Act or sold to the public through a
broker, dealer or market maker in compliance with Rule 144 under the Securities
Act (or any similar rule promulgated by the Securities Exchange Commission then
in force) or, solely in the case of Common Stock held by limited partners or
non-managing members of any private equity fund that has done a distribution of
Common Stock, at such point as the Registrable Securities are eligible to be
sold by such limited partners or non-managing members or their transferees
pursuant to Rule 144(k) under the Securities Act (or any similar rule
promulgated by the Securities Exchange Commission then in force).

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

                  "Securities Exchange Act" means the Securities Exchange Act of
1934, as amended from time to time.

                  "Vulcan Registrable Securities" means Registrable Securities
held by Vulcan or its successors and assigns.

                  9.       MISCELLANEOUS.

                  (a) No Inconsistent Agreements. Allegiance 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. Allegiance
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).




                                      -11-

Amended and Restated Registration Agreement Final
<PAGE>   12

                  (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 Allegiance and the holders of a majority of the
Investor Registrable Securities, the holders of a majority of the Management
Registrable Securities and the holders of a majority of the Vulcan Registrable
Securities; provided that if any such amendment or waiver would adversely affect
any holder of Registrable Securities relative to the holders of Investor
Registrable Securities, Management Registrable Securities or Vulcan 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.

                  (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. Notwithstanding
the foregoing, shares of Common Stock purchased by Vulcan pursuant to the Vulcan
Purchase Agreement shall be "Vulcan Registrable Securities" for purposes of this
Agreement and not "Investor Registrable Securities". Each of the parties hereto
agrees to be bound by Section 9 of the Vulcan Purchase Agreement.

                  (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.

                  (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


                                      -12-

Amended and Restated Registration Agreement Final
<PAGE>   13


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. In
the event 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. THE CORPORATE LAW OF THE STATE OF DELAWARE
SHALL GOVERN ALL ISSUES AND QUESTIONS CONCERNING THE RELATIVE RIGHTS OF
ALLEGIANCE AND ITS STOCKHOLDERS. ALL OTHER 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 (i) delivered
personally to the recipient, (ii) 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 (iii) one business day
after being sent to the recipient by reputable overnight courier service
(charges prepaid). Such notices, demands and other communications shall be sent
to Allegiance at the address set forth below and to any holder of Registrable
Securities at such address as indicated by Allegiance'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. Allegiance's address is:

           1950 N. Stemmons Freeway, Suite 3026
           Dallas, Texas 75207
           Attention:       Royce J. Holland
           Telephone:       (214) 261-7100
           Telecopy:        (214) 261-7107

           With a copy to:  Mark B. Tresnowski
                            Senior Vice President and General Counsel
                            4 Westbrook Corporate Center
                            Suite 400
                            Westchester, IL 60154
                            Telephone: (708) 836-5240
                            Telecopy: (708) 836-5250



                                      -13-


Amended and Restated Registration Agreement Final
<PAGE>   14


                  (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 in which Allegiance's chief-executive 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.


                                    * * * * *


                                      -14-

Amended and Restated Registration Agreement Final
<PAGE>   15



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


                            ALLEGIANCE TELECOM, INC.

                            By  /s/ MARK B. TRESNOWSKI
                                ------------------------------------------------

                            Name  Mark B. Tresnowski
                                  ----------------------------------------------

                            Its  Senior Vice President, General Counsel,
                                 -----------------------------------------------
                                 and Secretary
                                 -----------------------------------------------

                                /s/ C. DANIEL YOST
                                ------------------------------------------------
                                C. Daniel Yost


                                /s/ ROYCE J. HOLLAND
                                ------------------------------------------------
                                Royce J. Holland


                            ROYCE J. HOLLAND FAMILY LIMITED PARTNERSHIP


                            By  /s/ ROYCE J. HOLLAND
                                ------------------------------------------------
                                Royce J. Holland, its general partner


                                /s/ THOMAS M. LORD
                                ------------------------------------------------
                                Thomas M. Lord (individually, and on behalf of
                                Brian T. Lord and Colin J. Lord)


                            BATTERY VENTURES IV, L.P.
                            By Battery Partners IV, L.P., its general partner

                            By  /s/ RICHARD FRISBIE
                                ------------------------------------------------

                            Name  Richard Frisbie
                                  ----------------------------------------------

                            Its  Member Manager
                                 -----------------------------------------------


<PAGE>   16






 [Continuation of Signature Page to Amended and Restated Registration Agreement]

                            BATTERY INVESTMENT PARTNERS IV, LLC

                            By  /s/ RICHARD FRISBIE
                                ------------------------------------------------

                            Name  Richard Frisbie
                                  ----------------------------------------------

                            Its  Member Manager
                                 -----------------------------------------------


                            FRONTENAC VII LIMITED PARTNERSHIP
                            By Frontenac Company VII, LLC, its general partner

                            By  /s/ JAMES E. CRAWFORD, III
                                ------------------------------------------------

                            Name  James E. Crawford, III
                                  ----------------------------------------------

                            Its  Member
                                 -----------------------------------------------


                            FRONTENAC MASTERS VII LIMITED PARTNERSHIP
                            By Frontenac Company VII, LLC, its general partner

                            By  /s/ JAMES E. CRAWFORD, III
                                ------------------------------------------------

                            Name  James E. Crawford, III
                                  ----------------------------------------------

                            Its  Member
                                 -----------------------------------------------



                            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/ GARY J. LITTLE
                                ------------------------------------------------

                            Name  Gary J. Little
                                  ----------------------------------------------

                            Its  Chief Financial Officer
                                 -----------------------------------------------

<PAGE>   17

[Continuation of Signature Page to Amended and Restated Registration Agreement]


                            MORGAN STANLEY CAPITAL PARTNERS III, L.P.
                            By MSCP III, L.P., its general partner
                            By Morgan Stanley Capital Partners III, Inc., its
                            general partner

                            By  /s/ ALAN E. GOLDBERG
                                ------------------------------------------------

                            Name  Alan E. Goldberg
                                  ----------------------------------------------

                            Its  Chairman, CEO and Director
                                 -----------------------------------------------

                            By  /s/ JOHN B. EHRENKRANZ
                                ------------------------------------------------

                            Name  John B. EhrenKranz
                                  ----------------------------------------------

                            Its  Principal
                                 -----------------------------------------------

                            MSCP III 892 INVESTORS, L.P.
                            By MSCP III, L.P., its general partner
                            By Morgan Stanley Capital Partners III, Inc., its
                            general partner

                            By  /s/ ALAN E. GOLDBERG
                                ------------------------------------------------

                            Name  Alan E. Goldberg
                                  ----------------------------------------------

                            Its  Chairman, CEO and Director
                                 -----------------------------------------------

                            By  /s/ JOHN B. EHRENKRANZ
                                ------------------------------------------------

                            Name  John B. EhrenKranz
                                  ----------------------------------------------

                            Its  Principal
                                 -----------------------------------------------
<PAGE>   18
[Continuation of Signature Page to Amended and Restated Registration Agreement]






                            MORGAN STANLEY CAPITAL INVESTORS, L.P.
                            By MSCP III, L.P., its general partner
                            By Morgan Stanley Capital Partners III, Inc., its
                            general partner

                            By  /s/ ALAN E. GOLDBERG
                                ------------------------------------------------

                            Name  Alan E. Goldberg
                                  ----------------------------------------------

                            Its  Chairman, CEO and Director
                                 -----------------------------------------------

                            By  /s/ JOHN B. EHRENKRANZ
                                ------------------------------------------------

                            Name  John B. EhrenKranz
                                  ----------------------------------------------

                            Its  Principal
                                 -----------------------------------------------

                            VULCAN VENTURES INCORPORATED

                            By  /s/ WILLIAM D. SAVOY
                                ------------------------------------------------

                            Name  William D. Savoy
                                  ----------------------------------------------

                            Its  Vice President
                                 -----------------------------------------------


© 2022 IncJournal is not affiliated with or endorsed by the U.S. Securities and Exchange Commission