TC GROUP LLC
SC 13D, 1996-10-07
Previous: FLAG INVESTORS EQUITY PARTNERS FUND INC, 497, 1996-10-07
Next: US OFFICE PRODUCTS CO, 424B3, 1996-10-07



<PAGE>
 
                       SECURITIES AND EXCHANGE COMMISSION
                             Washington, D.C. 20549

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

                                  SCHEDULE 13D
                   Under the Securities Exchange Act of 1934

                       HIGHWAYMASTER COMMUNICATIONS, INC.
                     ---------------------------------------
                                (Name of Issuer)


                     Common Stock, Par Value $.01 Per Share
                     --------------------------------------
                         (Title of Class of Securities)


                                  CUSIP NUMBER
                                  431263 10 2
                                  -----------
                                 (CUSIP Number)


                                  Mark D. Ein
                               The Carlyle Group
                         1001 Pennsylvania Avenue, N.W.
                                Suite 220 South
                             Washington, D.C. 20004
                                (202) 347-2626
                        ------------------------------
                 (Name, Address and Telephone Number of Person
               Authorized to Receive Notices and Communications)

                                   Copies to:

                             Daniel T. Lennon, Esq.
                                Latham & Watkins
                         1001 Pennsylvania Avenue, N.W.
                                   Suite 1300
                             Washington, D.C. 20004
                                 (202) 637-2200

                               September 27, 1996
           --------------------------------------------------------
            (Date of Event which Requires Filing of this Statement)

                If the filing person has previously filed a statement on
                Schedule 13G to report the acquisition which is subject of this
                Schedule 13D, and is filing this statement because of Rule 13d-
                1(b)(3) or (4), check the following box: [ ]
                
                Check the following box if a fee is being paid with the
                statement: [X]

                                    Page 1 
<PAGE>
 
                                  SCHEDULE 13D



CUSIP No. 431263 10 2


1.   Name of Reporting Persons:

     Carlyle-HighwayMaster Investors, L.P.

     IRS Identification Number of Above Person:

     N/A

2.   Check the Appropriate Box if a Member of a Group           (a) [   ]
                                                                (b) [ X ]

3.   SEC Use Only

4.   Source of Funds

     OO
 
5.   Check Box if Disclosure of Legal Proceedings is 
      Required Pursuant to Items 2(d) or 2(e)                       [   ]

6.   Citizenship or Place of Organization

     Delaware

     Number of Shares Beneficially Owned by Each 
      Reporting Person with:
 
7.     Sole Voting Power:                                               0
                                                                ---------
 
8.     Shared Voting Power:                                     2,222,799
                                                                ---------
 
9.     Sole Dispositive Power:                                          0
                                                                ---------
 
10.    Shared Dispositive Power:                                2,222,799
                                                                ---------
 
11.  Aggregate Amount Beneficially Owned by Each 
     Reporting Person:       (See Item 6 Below)                 2,222,799
                                                                ---------

12.  Check Box if the Aggregate Amount in Row (11) 
     Excludes Certain Shares                                        [   ]

13.  Percent of Class Represented by Amount in Row (11):             9.0%
                                                                     --- 

14.  Type of Reporting Person:

     PN

                                    Page 2
<PAGE>
 
                                  SCHEDULE 13D



CUSIP No. 431263 10 2


1.   Name of Reporting Persons:

     Carlyle-HighwayMaster Investors II, L.P.

     IRS Identification Number of Above Person:

     N/A

2.   Check the Appropriate Box if a Member of a Group    (a) [   ]
                                                         (b) [ X ]

3.   SEC Use Only

4.   Source of Funds

     OO

5.   Check Box if Disclosure of Legal Proceedings is
     Required Pursuant to Items 2(d) or 2(e)               [     ]

6.   Citizenship or Place of Organization

     Delaware

     Number of Shares Beneficially Owned by Each 
      Reporting Person with:
 
7.   Sole Voting Power:                                         0
                                                           -------
 
8.   Shared Voting Power:                                  209,354
                                                           -------
 
9.   Sole Dispositive Power:                                     0
                                                           -------
 
10.  Shared Dispositive Power:                             209,354
                                                           -------
 
11.  Aggregate Amount Beneficially Owned by Each 
     Reporting Person:       (See Item 6 Below)            209,354
                                                           -------

12.  Check Box if the Aggregate Amount in Row (11)
     Excludes Certain Shares                                 [   ]

13.  Percent of Class Represented by Amount in Row (11):      0.8%
                                                              --- 

14.  Type of Reporting Person:

     PN

                                    Page 3
<PAGE>
 
                                  SCHEDULE 13D


CUSIP No. 431263 10 2
          -----------

1.   Name of Reporting Persons:

     TC Group, L.L.C.

     IRS Identification Number of Above Person:

     N/A

2.   Check the Appropriate Box if a Member of a Group                (a) [   ]
                                                                     (b) [ X ]

3.   SEC Use Only

4.   Source of Funds

     OO
 
5.   Check Box if Disclosure of Legal Proceedings is
     Required Pursuant to Items 2(d) or 2(e)                             [   ]

6.   Citizenship or Place of Organization

     Delaware

     Number of Shares Beneficially Owned by Each 
      Reporting Person with:
 
7.   Sole Voting Power:                                                      0
                                                                     ---------
 
8.   Shared Voting Power:                                            2,723,468
                                                                     ---------
 
9.   Sole Dispositive Power:                                                 0
                                                                     ---------
 
10.  Shared Dispositive Power:                                       2,723,468
                                                                     ---------
 
11.  Aggregate Amount Beneficially Owned  Reporting Person:       
     by Each             (See Item 6 Below)                          2,723,468
                                                                     ---------
 
12.  Check Box if the Aggregate Amount in Row (11)
     Excludes Certain Shares                                              [  ]
 
13.  Percent of Class Represented by Amount in Row (11):                  11.0%
                                                                     ---------
 
14.  Type of Reporting Person:               OO/*/

/*/  TC Group, L.L.C. is a limited liability company organized under the laws of
     the State of Delaware.

                                    Page 4
<PAGE>
 
                                  SCHEDULE 13D


CUSIP No. 431263 10 2
          -----------

1.   Name of Reporting Persons:

     TC Group Investment Holdings, L.L.C.

     IRS Identification Number of Above Person:

     N/A

2.   Check the Appropriate Box if a Member of a Group                (a) [   ]
                                                                     (b) [ X ]

3.   SEC Use Only

4.   Source of Funds

     OO
 
5.   Check Box if Disclosure of Legal Proceedings is
     Required Pursuant to Items 2(d) or 2(e)                             [   ]

6.   Citizenship or Place of Organization

     Delaware

     Number of Shares Beneficially Owned by Each Reporting 
     Person with:
 
7.   Sole Voting Power:                                                   0
                                                                       -------
 
8.   Shared Voting Power:                                              291,315
                                                                       -------
 
9.   Sole Dispositive Power:                                              0
                                                                       -------
 
10.  Shared Dispositive Power:                                         291,315
                                                                       -------
 
11.  Aggregate Amount Beneficially Owned by Each              
     Reporting Person:                      (See Item 6 Below)         291,315
                                                                       -------
 
12.  Check Box if the Aggregate Amount in Row (11)
     Excludes Certain Shares                                             [   ]
 
13.  Percent of Class Represented by Amount in Row (11):                  1.2%
                                                                          ---
 
14.  Type of Reporting Person:                 OO/**/

- -------------------------
/**/  TC Group Investment Holdings, L.L.C. is a limited liability company
      organized under the laws of the State of Delaware.

                                    Page 5
<PAGE>
 
                                  SCHEDULE 13D


CUSIP No. 431263 10 2
          -----------

1.   Name of Reporting Persons:

     TCG Holdings, L.L.C.

     IRS Identification Number of Above Person:

     N/A

2.   Check the Appropriate Box if a Member of a Group                (a) [   ]
                                                                     (b) [ X ]

3.   SEC Use Only

4.   Source of Funds

     OO
 
5.   Check Box if Disclosure of Legal Proceedings is
     Required Pursuant to Items 2(d) or 2(e)                             [   ]

6.   Citizenship or Place of Organization

     Delaware

     Number of Shares Beneficially Owned by Each Reporting Person with:
 
7.   Sole Voting Power:                                                  0
                                                                     ---------
 
8.   Shared Voting Power:                                            2,723,468
                                                                     ---------
 
9.   Sole Dispositive Power:                                             0
                                                                     ---------
 
10.  Shared Dispositive Power:                                       2,723,468
                                                                     ---------
 
11.  Aggregate Amount Beneficially Owned by Each       
     Reporting Person:               (See Item 6 Below)              2,723,468
                                                                     ---------
 
12.  Check Box if the Aggregate Amount in Row (11)
     Excludes Certain Shares                                             [    ]
 
13.  Percent of Class Represented by Amount in Row (11):                  11.0%
                                                                          ----
 
14.  Type of Reporting Person:               OO/***/


/***/  TCG Holdings, L.L.C. is a limited liability company organized under the
       laws of the State of Delaware.

                                    Page 6
<PAGE>
 
                                  SCHEDULE 13D


CUSIP No. 431263 10 2
          -----------

1.   Name of Reporting Persons:

     Mark D. Ein

     IRS Identification Number of Above Person:

     N/A

2.   Check the Appropriate Box if a Member of a Group                (a) [   ]
                                                                     (b) [ X ]

3.   SEC Use Only

4.   Source of Funds

     OO
 
5.   Check Box if Disclosure of Legal Proceedings is
     Required Pursuant to Items 2(d) or 2(e)                            [    ]

6.   Citizenship or Place of Organization

     United States citizen

     Number of Shares Beneficially Owned by Each 
      Reporting Person with:
 
7.   Sole Voting Power:                                                   0  
                                                                        ------
 
8.   Shared Voting Power:                                               28,611
                                                                        ------
 
9.   Sole Dispositive Power:                                            28,611
                                                                        ------
 
10.  Shared Dispositive Power:                                            0
                                                                        ------
 
11.  Aggregate Amount Beneficially Owned by Each              
     Reporting Person:                 (See Item 6 Below)               28,611
                                                                        ------
                                               
 
12.  Check Box if the Aggregate Amount in Row (11)
     Excludes Certain Shares                                            [    ]
 
13.  Percent of Class Represented by Amount in Row (11):                   0.1%
                                                                        ------
                                      
 
14.  Type of Reporting Person:       IN

                                    Page 7
<PAGE>
 
Item 1.   Security and Issuer.
- ------    ------------------- 

          The title of the class of equity securities to which this Schedule 13D
relates is the Common Stock, par value $.01 per share (the "Common Stock"), of
HighwayMaster Communications, Inc., a Delaware corporation (the "Company").  The
address of the Company is 16479 Dallas Parkway, Suite 710, Dallas, TX, 75248.


Item 2.   Identity and Background.
- ------    ----------------------- 

          (a)-(c), (f)  The names of the persons filing this Schedule 13D are
(i) Carlyle-HighwayMaster Investors, L.P., a Delaware limited partnership ("HM
Investors"), (ii) Carlyle-HighwayMaster Investors II, L.P., a Delaware limited
partnership ("HM Investors II"), (iii) TC Group, L.L.C., a Delaware limited
liability company ("TC Group"), (iv) TC Group Investment Holdings, L.L.C., a
Delaware limited liability company ("TCG Investment"), (v) TCG Holdings, L.L.C.,
a Delaware limited liability company ("TCG"), and (vi) Mark D. Ein, a United
States citizen (with HM Investors, HM Investors II, TC Group, TCG Investment,
TCG and Mr. Ein being collectively referred to herein as the "Reporting
Persons").

          TC Group is the sole general partner of HM Investors and HM Investors
II.  TCG is the managing member of each of TC Group and TCG Investment.  Mark D.
Ein is an officer of TCG.  William E. Conway, Jr., Frank C. Carlucci, III,
Daniel A. D'Aniello, Richard G. Darman, David M. Rubenstein and James A. Baker,
III (collectively, the "TCG Principals") are the executive officers of TCG and
managing members of TCG.  Each TCG Principal is a citizen and resident of the
United States.

          The principal business of each of HM Investors and HM Investors II is
investment in leveraged buyout transactions, venture capital situations and
other opportunities. The principal business of each of TC Group, TCG and TCG
Investment is that of a merchant and investment banking firm. The principal
occupation of each of Mark D. Ein and each TCG Principal other than James A.
Baker, III is the fulfillment of his duties as an officer of TCG. The principal
business of James A. Baker, III is senior partner at the law firm of Baker &
Botts, L.L.P. The business address of each of HM Investors, HM Investors II, TC
Group, TCG, Mark D. Ein, and each TCG Principal other than James A. Baker, III
is 1001 Pennsylvania Avenue, N.W., Suite 220 South, Washington, D.C. 20004. The
business address of James A. Baker, III is Baker & Botts, L.L.P., 1299
Pennsylvania Ave., N. W., Washington, D.C. 20004. The business address of TCG
Investment is 900 Market Street, Suite 200, Wilmington, Delaware, 19801.

          (d) and (e).  During the last five years, none of the Reporting
Persons, nor to the best knowledge of the Reporting Persons, none of the TCG
Principals, has (i) been convicted in a criminal proceeding (excluding traffic
violations or similar misdemeanors) or (ii) been a party to a civil proceeding
of a judicial or administrative body of competent jurisdiction and as a result
of such proceeding was or is subject to a judgment, decree or final order
enjoining future violations of, or 

                                    Page 8
<PAGE>
 
prohibiting or mandating activities subject to, federal or state securities laws
or finding any violation with respect to such laws.


Item 3.   Source and Amount of Funds or Other Consideration.
- ------    ------------------------------------------------- 

          On February 14, 1996, the Reporting Persons filed a Schedule 13G with
respect to the Company to report their holdings of shares of common stock, par
value $0.01 per share, of the Company (the "Common Stock") that were acquired by
the Reporting Persons in transactions prior to the initail public offering of
the Common Stock by the Company. These transactions were described in the
Registration Statement filed by the Company in connection with its initial
public offering. This Schedule 13D is being filed to report the acquisition of
additional shares of Common Stock by certain of the Reporting Persons which
occurred on September 27, 1996.

          The shares of Common Stock acquired that result in the filing of this
Schedule 13D were acquired as part of a recapitalization transaction of the
Company (the "Recapitalization") consummated on September 27, 1996 (the "Closing
Date").  On such date, certain promissory notes of the Company held by HM
Investors and HM Investors II (and other holders of similar promissory notes),
together with a portion of accrued but unpaid interest on such promissory notes,
were exchanged by the Company for shares of Common Stock.  No additional
consideration was paid by the holders for the exchange of such promissory notes
for shares of Common Stock.  Immediately prior to the consummation of the
Recapitalization, (i) HM Investors was the holder of promissory notes of the
Company in the original aggregate principal amount of $5,187,536.53 (the "HM
Investors Notes") and (ii) HM Investors II was the holder of promissory notes of
the Company in the original aggregate principal amount of $488,604.30 (the "HM
Investors II Notes").  On the Closing Date, pursuant to the Recapitalization,
(i) the Company issued to HM Investors in exchange for the HM Investors Notes
together with the amount of $25,866.62 in accrued but unpaid interest on the HM
Investors Notes, 417,072 shares of Common Stock, and (ii) the Company issued to
HM Investors II in exchange for the HM Investors II Notes together with the
amount of $2,436.33 in accrued but unpaid interest on the HM Investors II Notes,
39,283 shares of Common Stock.


Item 4.   Purpose of Transaction.
- ------    ---------------------- 

          All shares of the Common Stock held by the Reporting Persons are held
by the Reporting Persons for investment purposes.  Each Reporting Person may,
subject to the continuing evaluation of the factors discussed herein, acquire
from time to time additional shares of the Common Stock or other securities of
the Company in the open market or in privately negotiated transactions, by
exchange offer or otherwise.  Depending on the 

                                    Page 9
<PAGE>
 
factors discussed herein, each Reporting Person may, from time to time, retain
or sell all or a portion of his holdings of the shares of the Common Stock in
the open market or in privately negotiated transactions, including, in the case
of HM Investors, HM Investors II, TC Group, TCG and TCG Investment, by way of
distribution of some or all of such shares of Common Stock to their partners or
members, as applicable. Each Reporting Person may also have discussions with
management regarding methods of increasing sales, cash flow and profitability.
Any actions that any Reporting Person might undertake will be dependent upon
such person's review of numerous factors, including, among other things, the
availability of shares of the Common Stock for purchase and the price levels of
such shares; general market and economic conditions; ongoing evaluation of the
Company's business operations and prospects; the relative attractiveness of
alternative business and investment opportunities; the actions of the management
and the Board of Directors of the Company; and other future developments.

          Although the foregoing reflects activities presently contemplated by
each Reporting Person with respect to the Company, the foregoing is subject to
change at any time.

          Other than as described above, the Reporting Persons have no present
plans or proposals which relate to or would result in: (i) the acquisition by
any person of additional securities of the Company, or the disposition of
securities of the Company; (ii) an extraordinary corporate transaction, such as
a merger, reorganization or liquidation, involving the Company or any of its
subsidiaries; (iii) a sale or transfer of a material amount of assets of the
Company or any of its subsidiaries; (iv) any change in the present Board or
management of the Company, including any plans or proposals to change the number
or term of directors or to fill any existing vacancies on the Board (other than
the Amendment Proposal (as defined below)); (v) any material change in the
present capitalization or dividend policy of the Company; (vi) any other
material change in the Company's business or corporate structure; (vii) changes
in the Company's certificate of incorporation or by-laws or other actions which
may impede the acquisition of control of the Company by any persons; (viii)
causing a class of securities of the Company to be delisted from a national
securities exchange or to cease to be authorized to be quoted in an inter-dealer
quotation system of a registered national securities association; (ix) a class
of equity securities of the Company becoming eligible for termination of
registration pursuant to Section 12(g)(4) of the Securities Exchange Act of
1934, as amended; or (x) any action similar to those enumerated above.


Item 5.   Interest in Securities of the Issuer.
- ------    ------------------------------------ 

          (a) HM Investors is the record owner of 2,222,799 shares of the Common
Stock, which represent approximately 9.0% of the issued and outstanding shares
of the Common Stock.  HM 

                                    Page 10
<PAGE>
 
Investors II is the record owner of 209,354 shares of the Common Stock, which
represent approximately 0.8% of the issued and outstanding shares of the Common
Stock. TC Group is the sole general partner of HM Investors and HM Investors II,
in which capacity TC Group may be deemed to be beneficial owner of the shares of
the Common Stock owned by HM Investors and HM Investors II. TC Group is the
record holder of 291,315 shares of the Common Stock, which represent
approximately 1.2% of the issued and outstanding shares of the Common Stock and
which are held of record by TC Group for the benefit of TCG Investment. TCG is
the managing member of, and a holder of a controlling interest in, TC Group, the
sole general partner of HM Investors and HM Investors II, in which capacity TCG
may be deemed to be the beneficial owner of the shares of the Common Stock owned
of record by TC Group, HM Investors and HM Investors II. TCG is also the
managing member, and holder of a controlling interest in, of TC Group, in which
capacity TCG may be deemed to be the beneficial owner of shares of the Common
Stock owned beneficially and of record by TC Group. Mark D. Ein is the sole
beneficial owner of 28,611 shares of the Common Stock (representing 0.1% of the
issued and outstanding Common Stock), with sole power to direct the disposition
of such shares.

          (b) HM Investors is the beneficial owner of 2,222,799 shares of the
Common Stock and is deemed to share beneficial ownership of all such shares with
TC Group and TCG by reason of TC Group's status as the sole general partner of
HM Investors and TCG's status as the managing member, and holder of a
controlling interest in, of TC Group.

          HM Investors II is the beneficial owner of 209,354 shares of the
Common Stock and is deemed to share beneficial ownership of all such shares with
TC Group and TCG by reason of TC Group's status as the sole general partner of
HM Investors II and TCG's status as the managing member of, and holder of a
controlling interest in, TC Group.

          TC Group is the beneficial owner of 2,723,468 shares of the Common
Stock, inclusive of (i) 2,222,799 shares of the Common Stock owned directly by
HM Investors, (ii) 209,354 shares of the Common Stock owned directly by HM
Investors and (iii) 291,315 shares of the Common Stock held of record by TC
Group for the benefit of TCG Investment, and is deemed to share beneficial
ownership of all such shares with TCG by reason of TCG's status as managing
member, and holder of a controlling interest in, of TC Group.

          TCG Investment is the beneficial owner of 291,315 shares of the Common
Stock, inclusive of 291,315 shares of the Common Stock held of record by TC
Group for the benefit of TCG Investment.  TC Group shares the power to vote and
dispose of such shares, and accordingly, TCG Investment is deemed to share
beneficial ownership of all such shares with TC Group and TCG by reason of TC
Group's power to vote and dispose of such shares, 

                                    Page 11
<PAGE>
 
and by reason of TCG's status as managing member of, and holder of a controlling
interest in, TC Group and TCG Investment.

          TCG is the beneficial owner of 2,723,468 shares of the Common Stock,
inclusive of (i) 2,222,799 shares of the Common Stock owned of record by HM
Investors, (ii) 209,354 shares of the Common Stock owned of record by HM
Investors II and (iii) 291,315 shares of the Common Stock owned of record by TC
Group.

          Mark D. Ein is the sole beneficial owner of 28,611 shares of the
Common Stock.

          William E. Conway, Jr., Frank C. Carlucci, III, Daniel A. D'Aniello,
Richard G. Darman, David M. Rubenstein and James A. Baker, III are managing
members of TCG, and, in such capacity, such individuals may be deemed to share
beneficial ownership of any shares of Common Stock owned by TCG.  Such
individuals expressly disclaim any such beneficial ownership.

          (c)  See Item 3.

          (d) Except as provided in Item 6 below, no person other than the
Reporting Persons is known to the Reporting Persons to have the right to receive
or the power to direct the receipt of dividends from, or the proceeds from the
sale of, the shares of Common Stock of the Company owned by the Reporting
Persons.

          (e)  Not applicable.


Item 6.   Contracts, Arrangements, Understandings or Relationships with
- ------    -------------------------------------------------------------
Respect to Securities of the Issuer.
- ----------------------------------- 

          On September 27, 1996, the Company entered into certain transactions
with Southwestern Bell Wireless Holdings, Inc. ("SBWH"), including (i) the
issuance and sale by the Company to SBWH of shares of the Company's Series D
participating convertible preferred stock, par value $.01 per share, in exchange
for cash consideration in the amount of $20,000,000 and (ii) the issuance by the
Company to SBWH of warrants to purchase shares of Common Stock (the "SBWH
Investment").

          Concurrently with the SBWH Investment, each of HM Investors and HM
Investors II entered into a Recapitalization Agreement, dated as of September
27, 1996, by and among the Company and certain other stockholders of the Company
listed therein (the "Recapitalization Agreement"), pursuant to which, among
other things, (i) certain promissory notes of the Company held by HM Investors
and HM Investors II, together with a portion of the accrued and unpaid interest
thereon, were exchanged for shares of Common Stock and (ii) certain promissory
notes of the Company held by certain other stockholders of the Company, together
with a portion of the accrued and unpaid interest thereon, were exchanged for
shares of Common Stock.  A copy of 

                                    Page 12
<PAGE>
 
the Recapitalization Agreement is attached hereto as Exhibit 2 and incorporated
herein by reference.

          In connection with the SBWH Investment and the Recapitalization, the
Reporting Persons entered into an Amended and Restated Stockholders' Agreement,
dated September 27, 1996 (the "Stockholders' Agreement") by and among the
Company, HM Investors, HM Investors II, TC Group, SBWH, H.M. Rana Investments
Limited, Chase Manhattan Investment Holdings, Inc., Archery Partners, Clipper
Capital Associates, L.P., Clipper/Merchant Partners, L.P., Clipper/Merban, L.P.,
Erin Mills International Investment Corporation, The Erin Mills Investment
Corporation, Mark D. Ein, William C. Kennedy, Donald M. Kennedy, William C.
Saunders, Robert T. Hayes and Robert S. Folsom.  Pursuant to the Stockholders'
Agreement, the parties thereto have agreed to, among other things, vote each
share of the Common Stock owned in favor of the election of directors designated
by certain parties to the Stockholders' Agreement, including one individual
designated by the Reporting Persons. Under the stockholders' Agreement the
Company has agreed to register the shares of Common Stock received pursuant to
the Recapitalization with the Securities and Exchange Commission, subject to
certain timing considerations. As a result of the Stockholders' Agreement, the
parties thereto may be deemed to be members of a "group" within the meaning of
Rule 13d-5(b)(1) promulgated under the Securities Exchange Act of 1934 and,
accordingly, may be deemed to be the beneficial owners of all shares of the
Common Stock subject to the Agreement. In total, 20,617,328 shares of the Common
Stock, representing approximately 83.3% of the outstanding shares of the Common
Stock, are subject to the Stockholders' Agreement. HM Investors, HM Investors
II, TC Group, TCG, TCG Investment and Mark D. Ein do not affirm the existence of
such a group and expressly disclaim beneficial ownership of the shares of the
Common Stock held by the other parties to the Stockholders' Agreement. A copy of
the Stockholders' Agreement is attached hereto as Exhibit 3 and incorporated
herein by reference. The Reporting Persons have made a proposal to the Company
to amend the Stockholders' Agreement (the "Amendment Proposal") to (i) release
the Reporting Persons from any obligation to vote in favor of the election to
the Board of Directors of the Company of any person nominated by any stockholder
and (ii) cause the Reporting Persons to cease to have any right to cause the
other stockholders party to the Stockholders Agreement to vote in favor of any
individuals nominated for election to the Board of Directors of the Company by
the Reporting Persons. It is anticipated that Mr. Ein would resign from the
Board of Directors upon implementation of the Amendment Proposal.

          In connection with the SBWH Investment, each of HM Investors, HM
Investors II and TC Group granted an irrevocable proxy to SBWH on September 30,
1996, granting SBWH the right to vote the shares of Common Stock held by each
such party on such date in favor of approval of an amendment to the Company's
Certification of Incorporation authorizing additional shares of capital stock of
the Company and in favor of the approval of the 

                                    Page 13
<PAGE>
 
issuance by the Company to SBWH of shares of Common Stock upon the exercise of
certain warrants to purchase up to 5,000,000 shares of Common Stock held by
SBWH. A copy of each Irrevocable Proxy granted by HM Investors, HM Investors II
and TC Group is attached hereto as Exhibit 4 and incorporated herein by
reference.

          Under certain circumstances, 979, 54,552, and 55,251 shares of Common
Stock held of record by TC Group are subject to forfeiture to Clipper Capital
Associates, L.P., Clipper/Merchant Partners, L.P. and Clipper/Merban, L.P.,
respectively, pursuant to a co-investment agreement entered into among such
parties and TC Group.


Item 7.   Material to be Filed as Exhibits.
- ------    -------------------------------- 

Exhibit 1.     Joint Filing Agreement dated as of October 7, 1996, by and among
               Carlyle-HighwayMaster Investors, L.P., Carlyle-HighwayMaster
               Investors II, L.P., TC Group, L.L.C., TC Group Investment
               Holdings, L.L.C., TCG Holdings, L.L.C. and Mark D. Ein.

Exhibit 2.     Recapitalization Agreement, dated as of September 27, 1996, by
               and among HighwayMaster Communications, Inc., Clipper Capital
               Associates, L.P., Clipper/Merban, L.P., Clipper/Merchant
               Partners, L.P., Carlyle-HighwayMaster Investors, L.P., Carlyle-
               HighwayMaster Investors II, L.P., Chase Manhattan Investment
               Holdings, Inc., H.M. Rana Investments Limited, Archery Partners,
               The Erin Mills Investment Corporation, The Erin Mills Development
               Corporation, Erin Mills International Investment Corporation,
               Robert T. Hayes and Robert S. Folsom.

Exhibit 3.     Amended and Restated Stockholders' Agreement, dated as of
               September 27, 1996, by and among HighwayMaster Communications,
               Inc. and each of the stockholders identified therein.

Exhibit 4.     Irrevocable Proxy, dated September 30, 1996, of each of Carlyle-
               HighwayMaster Investors, L.P., Carlyle-HighwayMaster Investors
               II, L.P. and TC Group, L.L.C.

                                    Page 14
<PAGE>
 
                                   SIGNATURE
                                   ---------

          After reasonable inquiry and to the best of the knowledge and belief
of the undersigned, the undersigned certify that the information set forth in
this statement is true, complete and correct.


Dated:  October 7, 1996  CARLYLE-HIGHWAYMASTER INVESTORS, L.P.

                              By:   TC Group, L.L.C., its General Partner

                                    By:  TCG Holdings, L.L.C., its Managing
                                         Member



                                    By: /s/ Richard G. Darman 
                                        -------------------------
                                         Name:  Richard G. Darman 
                                                -----------------
                                         Title: Managing Director 
                                                -----------------

                         CARLYLE-HIGHWAYMASTER INVESTORS II, L.P.

                              By:   TC Group, L.L.C., its General Partner

                                    By:  TCG Holdings, L.L.C., its Managing
                                         Member


                                    By: /s/ Richard G. Darman 
                                        -------------------------
                                         Name:  Richard G. Darman 
                                                -----------------
                                         Title: Managing Director 
                                                -----------------


                         TC GROUP, L.L.C.

                              By:   TCG Holdings, L.L.C., its Managing Member


                                    By: /s/ Richard G. Darman 
                                        -------------------------
                                         Name:  Richard G. Darman 
                                                -----------------
                                         Title: Managing Director 
                                                -----------------


                                    Page 15
 

<PAGE>
 
                         TC GROUP INVESTMENT HOLDINGS, L.L.C.

                              By:   TCG Holdings, L.L.C., its Managing Member



                                    By:  /s/ Richard G. Darman
                                         -------------------------
                                         Name:  Richard G. Darman
                                                ------------------
                                         Title: Manager Director
                                                ------------------



                         TCG HOLDINGS, L.L.C.

                              By:   TCG Holdings, L.L.C., its Managing Member



                                    By:  /s/ Richard G. Darman
                                         -------------------------
                                         Name:  Richard G. Darman
                                                ------------------
                                         Title: Manager Director
                                                ------------------


                         /s/ Mark D. Ein
                         -----------------------------------------
                         MARK D. EIN

                                    Page 16
<PAGE>
 
                                 EXHIBIT INDEX
                                 -------------
<TABLE>
<CAPTION>
 
 
                                                          
                                                          
<S>            <C>                                        
                                                          
Exhibit 1.     Joint Filing Agreement dated as of         
               October 7, 1996, by and among              
               Carlyle-HighwayMaster Investors,           
               L.P., Carlyle-HighwayMaster                
               Investors II, L.P., TC Group,              
               L.L.C., TC Group Investment                
               Holdings, L.L.C., TCG Holdings,            
               L.L.C. and Mark D. Ein.                    
                                                          
Exhibit 2.     Recapitalization Agreement, dated          
               as of September 27, 1996, by and           
               among HighwayMaster                        
               Communications, Inc., Clipper              
               Capital Associates, L.P.,                  
               Clipper/Merban, L.P.,                      
               Clipper/Merchant Partners, L.P.,           
               Carlyle-HighwayMaster Investors,           
               L.P., Carlyle-HighwayMaster                
               Investors II, L.P., Chase                  
               Manhattan Investment Holdings,             
               Inc., H.M. Rana Investments                
               Limited, Archery Partners, The             
               Erin Mills Investment Corporation,         
               The Erin Mills Development                 
               Corporation, Erin Mills                    
               International Investment                   
               Corporation, Robert T. Hayes and           
               Robert S. Folsom.                          
                                                          
Exhibit 3.     Amended and Restated Stockholders'         
               Agreement, dated as of September           
               27, 1996, by and among                     
               HighwayMaster Communications, Inc.         
               and each of the stockholders               
               identified therein.                        
                                                          
Exhibit 4.     Irrevocable Proxy, dated                 
               September 30, 1996, of each of 
               Carlyle-HighwayMaster Investors, 
               L.P., Carlyle-HighwayMaster
               Investors II, L.P. and TC Group, L.L.C.
</TABLE>

                                    Page 17

<PAGE>
 
                                   EXHIBIT 1

                             JOINT FILING AGREEMENT
                             ----------------------


          In accordance with Rule 13d-1(f) promulgated under the Securities
Exchange Act of 1934, as amended, the undersigned hereby agree to the joint
filing with all other Reporting Persons (as such term is defined in the Schedule
13D referred to below) on behalf of each of them of a statement on Schedule 13D
(including amendments thereto) with respect to the common stock, par value $.01
per share, of HighwayMaster Communications, Inc., a Delaware corporation, and
that this Agreement may be included as an Exhibit to such joint filing.  This
Agreement may be executed in any number of counterparts, all of which taken
together shall constitute one and the same instrument.

          [Remainder of this page has intentionally been left blank.]
<PAGE>
 
   IN WITNESS WHEREOF, the undersigned hereby execute this Agreement as of the
7th day of October, 1996.


Dated:  October 7, 1996  CARLYLE-HIGHWAYMASTER INVESTORS, L.P.

                              By:   TC Group, L.L.C., its General Partner

                                    By:  TCG Holdings, L.L.C., its Managing
                                         Member


 
                                    By: /s/ Richard G. Darman
                                       -------------------------
                                         Name: Richard G. Darman
                                              ------------------
                                         Title: Managing Director
                                               ------------------ 


                         CARLYLE-HIGHWAYMASTER INVESTORS II, L.P.

                              By:   TC Group, L.L.C., its General Partner

                                    By:  TCG Holdings, L.L.C., its Managing
                                         Member


                                    By: /s/ Richard G. Darman   
                                       -------------------------
                                         Name: Richard G. Darman
                                              ------------------ 
                                         Title: Managing Director
                                               ------------------

                        TC GROUP, L.L.C.

                              By:   TCG Holdings, L.L.C., its Managing Member



                                    By: /s/ Richard G. Darman   
                                       -------------------------
                                         Name: Richard G. Darman
                                              ------------------ 
                                         Title: Managing Director
                                               ------------------
<PAGE>
 
                         TC GROUP INVESTMENT HOLDINGS, L.L.C.

                              By:   TCG Holdings, L.L.C., its Managing Member



                                    By: /s/ Richard G. Darman   
                                       -------------------------
                                         Name: Richard G. Darman
                                              ------------------ 
                                         Title: Managing Director
                                               ------------------



                         TCG HOLDINGS, L.L.C.

                              By:   TCG Holdings, L.L.C., its Managing Member



                                    By: /s/ Richard G. Darman   
                                       -------------------------
                                         Name: Richard G. Darman
                                              ------------------ 
                                         Title: Managing Director
                                               ------------------


                         /s/ Mark D. Ein
                         ------------------------------------
                         MARK D. EIN

<PAGE>
 
                                   Exhibit 2


                          RECAPITALIZATION AGREEMENT

                This RECAPITALIZATION AGREEMENT (the "Agreement"), entered into
                                                      ---------  
as of September ___, 1996, by and between HIGHWAYMASTER COMMUNICATIONS, INC., a
Delaware corporation (the "Company"), and each of the entities and persons
                           -------
listed on Exhibit A attached to this Agreement as Carlyle stockholders (the
          --------- 
"Carlyle Stockholders") and each of the entities and persons listed on Exhibit A
 --------------------
attached to this Agreement as Erin Mills Stockholders (the "Erin Mills
                                                            ----------
Stockholders").
- ------------
                                  BACKGROUND

                Certain of the Carlyle Stockholders beneficially own
approximately 10.3% of the issued and outstanding shares of common stock, par
value $.01 per share (the "Common Stock"), of the Company.
                           ------------
                Certain of the Erin Mills Stockholders beneficially own
approximately 37.6% of the issued and outstanding shares of Common Stock.

                The Erin Mills Investment Corporation ("EMIC") is the holder
                                                        ----
of promissory notes dated August 23, 1996 and September 16, 1996 in the
aggregate original principal amount of $5,000,000 (the "Bridge Notes") issued
                                                        ------------
pursuant to a Note Purchase Agreement dated August 23, 1996 between the Company
and EMIC (the "Bridge Note Agreement")
               ---------------------         

                The Erin Mills Development Corporation is the holder of
929.105 shares of Series B Preferred Stock, par value $.01 per share (the
"Series B Preferred Stock"), of the Company. Robert S. Folsom is the holder of
 ------------------------
42.85 shares of Series B Preferred Stock. Robert T. Hayes is the holder of
108.0450 shares of Series B Preferred Stock. The holders of shares of Series B
Preferred Stock are collectively referred to as the "Series B Preferred
                                                     ------------------   
Stockholders."
- ------------
                Clipper Capital Associates, L.P. is the holder of promissory
notes dated June 28, 1995 in the original aggregate principal amount of
$29,871.76 (together, "Carlyle Note No. 1") issued by the Company pursuant to
                       ------------------ 
the Note Exchange and Amendments Agreement dated May 26, 1995 (the "Note
                                                                    ----    
Exchange Agreement"). Clipper/Merban, L.P. is the holder of promissory notes
- ------------------        
dated June 28, 1995 in the original aggregate principal amount of $1,684,009.32
(together, "Carlyle Note No. 2") issued by the Company pursuant to the Note
            ------------------    
Exchange Agreement. Clipper/Merchant Partners, L.P. is the holder of promissory
notes dated June 28, 1995 in the original aggregate principal amount of
$1,662,712.05 (together, "Carlyle Note No. 3 ") issued by the Company pursuant
                          ------------------
to the Note Exchange Agreement. Carlyle-HighwayMaster Investors, L.P. is the
holder of promissory notes dated June 28, 1995 in the original aggregate
principal amount of $5,187,536.53 (together, "Carlyle Note No. 4") issued by the
                                              ------------------  
Company pursuant to the Note Exchange Agreement. Carlyle-HighwayMaster Investors
II, L.P. is the holder of promissory notes dated June 28, 1995 in the original
aggregate principal amount of $488,604.30 (together, "Carlyle Note No. 5")
                                                      ------------------  
issued by the Company pursuant to the Note Exchange Agreement. Chase Manhattan
Investment Holdings, Inc. is the holder of promissory notes dated June 28, 1995
in the original aggregate principal amount of $1,241,756.43 ) (together,
"Carlyle Note No. 6") issued by the Company pursuant to the Note Exchange
 ------------------       
Agreement. H.M. Rana Investments Limited is the 
<PAGE>
 
holder of promissory notes dated June 28, 1995 in the original aggregate
principal amount of $1,810,378.26 (together, "Carlyle Note No. 7") issued by the
                                              ------------------  
Company pursuant to the Note Exchange Agreement. Archery Partners is the holder
of promissory notes dated June 28, 1995 in the original aggregate principal
amount of $215,218.08 (together, "Carlyle Note No. 8") issued by the Company
                                  ------------------      
pursuant to the Note Exchange Agreement. The Carlyle Note No. 1, Carlyle Note
No. 2, Carlyle Note No. 3, Carlyle Note No. 4, Carlyle Note No. 5, Carlyle Note
No. 6, Carlyle Note No. 7 and Carlyle Note No. 8 are collectively referred to
as the "Carlyle Notes." The holders of the Carlyle Notes are hereinafter
        -------------
collectively referred to as the "Carlyle Noteholders."
                                -------------------

                Concurrently with the execution and delivery of this
Agreement, the Company is entering into certain transactions (the "Investment
                                                                   ----------
Transactions") with Southwestern Bell Wireless Holdings, Inc. (the "Investor").
- ------------                                                        --------    
The Investment Transactions include, but are not limited to, (i) the issuance
and sale by the Company of 1,000 shares of its Series D Participating
Convertible Preferred Stock, par value $.01 per share, to the Investor pursuant
to a Purchase Agreement (the "Purchase Agreement") in exchange for a payment in
                              ------------------  
the amount of $20,000,000, (ii) the execution and delivery of an Amended and
Restated Stockholders' Agreement (the "Stockholders' Agreement") among the
                                       ----------------------- 
Company, the Carlyle Stockholders, the Erin Mills Stockholders, the Investor and
certain other stockholders of the Company, (iii) the agreement on the part of
the Investor to provide certain services to the Company pursuant to a Technical
Services Agreement (the "Technical Services Agreement") and (iv) the issuance by
                         ----------------------------   
the Company to the Investor of warrants to purchase an aggregate of 5,000,000
shares of Common Stock evidenced by a Warrant Certificate (the "Warrant
                                                                -------  
Certificate"). The Purchase Agreement, the Stockholders' Agreement, the
- -----------
Technical Services Agreement, and the Warrant Certificate are collectively
referred to as the "Investment Documents." Copies of the Investment Documents
                    --------------------    
have been provided by the Company to each of the other parties to this
Agreement.

                In order, among other things, to induce the Investor to enter
into the Investment Transactions, (1) Erin Mills International Investment
Corporation ("EMIIC") is willing to invest $10,000,000 in cash in Common Stock,
              -----  
(ii) the Series B Preferred Stockholders are willing to exchange the shares of
Series B Preferred Stock owned by them for shares of Common Stock on the basis
described in this Agreement, and (iii) the Carlyle Noteholders are willing to
exchange the Carlyle Notes for shares of Common Stock on the basis described in
this Agreement, in each case upon the terms and conditions set forth in this
Agreement

                NOW, THEREFORE, in consideration of the foregoing and the
respective representations, warranties, covenants, and agreements set forth in
this Agreement and other good and valuable consideration, the receipt and
sufficiency of which are hereby acknowledged, the parties to this Agreement
agree as follows:

                SECTION  1.     Recapitalization
                                ----------------

                (a)     Concurrently with the execution and delivery of this
Agreement, the Company will repay in full the principal amount of and all
interest accrued on, the Bridge Notes and EMIIC will surrender the Bridge Notes
to the Company for cancellation.

                                       2
<PAGE>
 
                (b)     Concurrently with the execution and delivery of this
Agreement, the Company will issue, sell, and deliver (against payment of the A
Purchase Price (as defined below)) to EMIIC, and EMIIC will purchase, accept,
and receive from the Company, 800,000 shares of Common Stock, free and clear of
all liens, claims and encumbrances. The purchase price (the "A Purchase Price")
                                                             ----------------   
for such 800,000 shares of Common Stock will be US$10,000,000, which will be
paid by EMIIC to the Company in immediately available funds on the date of this
Agreement.

                (c)     Concurrently with the execution and delivery of this
Agreement, the Company will issue, sell and deliver (against payment of the B
Purchase Price (as defined below)) to the several Erin Mills Stockholders set
forth on Exhibit B attached to this Agreement, and such Erin Mills Stockholders
         ---------
severally will purchase, accept and receive from the Company, the number of
shares of Common Stock set forth opposite their names on such exhibit (the "B
                                                                            -
Stock"), free and clear of all liens, claims and encumbrances. The purchase
- -----        
price (the "B Purchase Price") for the B Stock will be paid by the several Erin
            ----------------    
Mills Stockholders on the date of this Agreement by surrender to the Company of
the number of shares of Series B Preferred Stock set forth on Exhibit B attached
                                                              ---------
to this Agreement, duly endorsed in blank or accompanied by duly executed blank
stock powers, which shares will be free and clear of all liens, claims, and
encumbrances.

                                       3
<PAGE>
 
                (d)     Concurrently with the execution and delivery of this
Agreement, the Company will issue, sell, and deliver (against payment of the C
Purchase Price (as defined below)) to the Carlyle Noteholders, and the Carlyle
Noteholders severally will purchase, accept and receive from the Company, the
number of shares of Common Stock determined by dividing (i) the sum of the
principal amount of the Carlyle Notes held by each Carlyle Noteholder as set
forth in the recitals to this Agreement and the amount of interest accrued and
unpaid on each Carlyle Note set forth on Exhibit C hereto (the "Excluded
                                         ---------              --------
Interest") by (ii) $12.50 (the "C Shares"), free and clear of all liens, claims,
- ---------                      ----------
and encumbrances. The purchase price (the "C Purchase Price") for the C Shares
                                           -----------------
will be paid by the several Carlyle Stockholders on the date of this Agreement
by surrender to the Company of each of the Carlyle Notes for cancellation, which
notes will be free and clear of all liens, claims, and encumbrances. No
fractional shares or scrip representing fractional shares will be issued upon
the exchange of the Carlyle Notes for the C Shares in accordance with this
Section 1(d). If any such exchange would require the issuance of a fractional
- ------------
share, an amount equal to such fraction multiplied by the Closing Price (as
defined below) of the Common Stock on the trading day immediately preceding the
date of this Agreement will be paid to the holder in cash by the Company. In
addition, concurrently with the execution and delivery of this Agreement, the
Company will pay to the Carlyle Noteholders in cash on the date hereof all
accrued and unpaid interest on the Carlyle Notes, other than the Excluded
Interest. As used herein, the term "Closing Price" shall mean on any day the
reported last sale price per share of Common Stock regular way on such day or,
in case no such sale takes place on such day, the average of the reported
closing bid and asked prices regular way, in each case on the New York Stock
Exchange, or, if the shares of Common Stock are not listed or admitted to
trading on such Exchange, the principal national securities exchange on which
the shares of Common Stock are listed or admitted to trading or, if the Common
Stock is not listed or admitted to trading, on any national securities exchange,
the last quoted sale price or, if not so quoted, the average of the closing bid
and asked prices quoted on the Nasdaq National Market, or, if no so quoted, the
average of the closing bid and asked prices as furnished by any member of the
National Association of Securities Dealers, Inc. selected from time to time by
the corporation for that purpose.

                (e)     The closing of the transactions provided for in this
Section 1 (the "Closing" will take place at the offices of the Company (or at
- ---------      ---------
such other place as is specified by the Company) on the date of this Agreement.

SECTION 2.      Terminated Documents. Effective upon the execution and delivery
                --------------------
of this Agreement and without any other action, each of the Carlyle Stockholders
and the Erin Mills Stockholders, severally and not jointly, hereby (a) agrees
that the Terminated Documents (as defined below) will terminate and be of no
further force and effect and that it will have no further rights thereunder; and
(b) represents and warrants with respect to itself that it has not transferred
any of its rights or interests under or in respect of the Terminated Documents
and that such party has the sole right, capacity, and exclusive authority to
terminate its rights under the Terminated Documents. As used in this Agreement,
the term "Terminated Documents" means (i) the Subscription Agreement dated as of
          --------------------
February 4, 1994 by and among the Company (formerly known as HM Holding
Corporation) and the other parties named in such agreement, as amended to the
date of this Agreement, (ii) the Bridge Note and the Bridge Note Agreement, and
(iii) the Carlyle Notes

                                       4
<PAGE>
 
SECTION 3.      Investment Intent. Each of the Carlyle Stockholders and the Erin
                -----------------
Mills Stockholders hereby severally and not jointly represents and warrants to
the Company that the shares of Common Stock to be acquired by the such party
pursuant to this Agreement are to be acquired for the such party's own account
for investment and not with a view to, or for resale in connection with, any
distribution of such shares within the meaning of the Securities Act of 1933, as
amended (the "Securities Act" ).

SECTION 4.      Investor Status. In connection with the purchase of the shares
                ---------------
of Common Stock, each of the Erin Mills Stockholders and the Carlyle
Stockholders hereby severally and not jointly represents and warrants to the
Company with respect to itself as follow s

                (a)     Such party acknowledges that the shares of Common Stock
are not registered under the Securities Act or any applicable state securities
law, and that such shares may not be transferred or sold except pursuant to the
registration provisions of the Securities Act or pursuant to an applicable
exemption therefrom and pursuant to such state securities laws and regulations
as may be applicable.

                (b)     Such party is knowledgeable, sophisticated, and
experienced in business and financial matters of the type contemplated by this
Agreement and is able to bear the economic risks associated with its investment
in the Company. Such party has been afforded access to information regarding the
Company and its subsidiaries and their respective financial condition, operating
results, properties, liabilities, operations, and management sufficient to
enable it to evaluate the risks and merits of its investment in the Company.

SECTION 5.      Other Representations of the Erin Mills Stockholders. Each of
                ----------------------------------------------------
the Erin Mills Stockholders hereby further severally and not jointly represents
and warrants to the Company with respect to itself as follows:

                                       5
<PAGE>
 
                (a)     The execution, delivery and performance of this
Agreement and the consummation of the transactions contemplated by this
Agreement have been duly authorized by such Erin Mills Stockholder. This
Agreement has been duly executed by such Erin Mills Stockholder and constitutes
a valid and binding obligation of such Erin Mills Stockholder, enforceable in
accordance with its terms.

                (b)     The execution, delivery, and performance by such Erin
Mills Stockholder of this Agreement and the consummation of the transactions
contemplated by this Agreement: (i) is within such Erin Mills Stockholder's
corporate or partnership power and authority and has been duly authorized by all
necessary corporate or partnership action on the part of such Erin Mills
Stockholder, as appropriate; (ii) does not and will not conflict with or
contravene the terms of or require any consent, authorization, or approval
pursuant to such Erin Mills Stockholder's certificate of incorporation or
bylaws, partnership agreement or similar organizational document; (iii) does not
and will not violate, conflict with, or result in any breach or
contravention of or require any consent, authorization, approval, exemption, or
other action by or notice or declaration to, or filing with, any court or
administrative or governmental body or agency or other person pursuant to 
(A) any material agreement, lease, or contract of such Erin Mills Stockholder,
or (B) any applicable statute or any rule or regulation of any governmental
authority or any order or decree applicable to such Erin Mills Stockholder.

      SECTION 6.      Other Representations of the Carlyle Stockholders. Each 
                      -------------------------------------------------
of the Carlyle Stockholders hereby further severally and not jointly represents
and warrants to the Company with respect to itself as follows:

                (a)     The execution, delivery and performance of this
Agreement and the consummation of the transactions contemplated by this
Agreement have been duly authorized by such Carlyle Stockholder. This Agreement
has been duly executed by such Carlyle Stockholder and constitutes a valid and
binding obligation of such Carlyle Stockholder, enforceable in accordance with
its terms.

                (b)     The execution, delivery, and performance by such Carlyle
Stockholder of this Agreement and the consummation of the transactions
contemplated by this Agreement: (i) is within such Carlyle Stockholder's
corporate or partnership power and authority and has been duly authorized by all
necessary corporate or partnership action on the part of such Carlyle
Stockholder, as appropriate; (ii) does not and will not conflict with or
contravene the terms of or require any consent, authorization, or approval
pursuant to such Carlyle Stockholder's certificate of incorporation or bylaws,
partnership agreement or similar organizational document; (iii) does not and
will not violate, conflict with, or result in any breach or contravention of or
require any consent, authorization, approval, exemption, or other action by or
notice or declaration to, or filing with, any court or administrative or
governmental body or agency or other person pursuant to (A) any material
agreement, lease, or contract of such Carlyle Stockholder, or (B) any applicable
statute or any rule or regulation of any governmental authority or any order or
decree applicable to such Carlyle Stockholder.

                                       6
<PAGE>
 
     SECTION 7. Representations of the Company. The Company hereby represents
                ------------------------------
and warrants to each of the Carlyle Stockholders and the Erin Mills Stockholders
as follows:

                (a)     The execution, delivery, and performance of this
Agreement and the consummation of the transactions contemplated by this
Agreement have been duly authorized by the Company. This Agreement has been duly
executed by the Company and constitutes a valid and binding obligation of the
Company, enforceable in accordance with its terms. All outstanding shares of the
Company's capital stock are, and the shares of Common Stock to be issued to the
several Carlyle Stockholders and Erin Mills Stockholders will be upon such
issuance and receipt by the Company of payment therefor, duly authorized, fully
paid, and nonassessable. The offer, sale, and issuance of the Common Stock to
the several Carlyle Stockholders and the Erin Mills Stockholders under this
Agreement do not require registration under the Securities Act or any applicable
state securities laws or blue sky laws, assuming that all representations made
by the Carlyle Stockholders and the Erin Mills Stockholders in Sections 3 and 4
                                                               ---------      - 
are true.

                (b)     Each of the representations made by the Company in
Section 3 of the Purchase Agreement is true and correct and is incorporated by
this reference into this Agreement, except that (i) the Company makes no
representation to the Erin Mills Stockholders or the Carlyle Stockholders as to
the matters set forth in the first two sentences of Section 3(b)(iii) or in
Section 3(b)(iv) of the Purchase Agreement; and (ii) each reference to
"prejudice in any material respect the rights of the Investor under any of the
Transaction Documents" will be deemed to read as "prejudice in any material
respect the rights of the Carlyle Stockholders or the Erin Mills Stockholders
under this Agreement."

     SECTION 8. Survival and Indemnification.
                ----------------------------

                (a)     Survival of Representations, Warranties, Covenants, and
                        -------------------------------------------------------
Agreements; Knowledge of Breach. Notwithstanding any otherwise applicable
- -------------------------------
statute of limitation, the representations and warranties of the Company
included or provided for in this Agreement will survive the execution and
delivery of this Agreement until the expiration of nine months after the receipt
by the Erin Mills Stockholders and the Carlyle Stockholders of audited
consolidated financial statements for the Company, as of and for the year ending
December 31, 1996, together with a report thereon by the Company's independent
public accountants; provided, however, that any representation, warranty,
                    --------  --------    
covenant, or agreement contained in Sections 3(j) and 3(n) of the Purchase
Agreement and incorporated by reference in this Agreement will survive the
execution and delivery of this Agreement until the expiration of the applicable
statute of limitations (including any waivers or extensions thereof) with
respect to such matters, provided, further, that the provisions of this Section
                         --------  -------                              -------
8 will constitute the exclusive remedy on the part of the Erin Mills
- -
Stockholders and the Carlyle Stockholders in respect of a breach of the
representations and warranties of the Company contained in this Agreement. The
covenants and other agreements contained in this Agreement will survive the
execution and delivery of this Agreement until the date or dates specified in
such covenant or agreement or the expiration of the applicable statute of
limitations (including any waivers or extensions thereof) with respect to such
matters, whichever is later. In no event will the Company be liable (i) to the
Carlyle Stockholders for any breach of 

                                       7
<PAGE>
 
the representations, warranties, covenants, and agreements included or provided
for in this Agreement or other document delivered pursuant to this Agreement,
unless and until all claims for which aggregate damages are recoverable under
this Agreement by the Carlyle Stockholders exceed the product of (x) $250,000
and (y) a fraction the numerator of which is the total numbers of shares of
Common Stock issued to the Carlyle Stockholders pursuant to this Agreement and
the denominator is the total number of shares issued by the Company pursuant to
this Agreement (the "Carlyle Stockholder Deductible") or (ii) to the Erin Mills
                     ------------------------------   
Stockholders for any breach of the representations, warranties, covenants, and
agreements included or provided for in this Agreement or other document
delivered pursuant to this Agreement, unless and until all claims for which
aggregate damages are recoverable under this Agreement by the Erin Mills
Stockholders exceed the product of (x) $250,000 and (y) a fraction the numerator
of which is the total numbers of shares of Common Stock issued to the Erin Mills
Stockholders pursuant to this Agreement and the denominator is the total number
of shares issued by the Company pursuant to this Agreement (the "Erin Mills
                                                                 ----------
Stockholder Deductible"), in which case such party will be entitled to damages
- ----------------------
equal to such excess, but, in the case of the Carlyle Stockholders and the Erin
Mills Stockholders, not more than the purchase price paid by such party for the
Common Stock acquired under this Agreement by such party plus the charges and
expenses (including reasonable attorneys' fees and expenses) incurred by such
party sustaining such damages in connection with this Agreement and the
transactions contemplated hereby-;

                (b)     Indemnification. For a period commencing on the date of
                        ---------------
this Agreement and ending, as the case may be, upon the expiration of the
periods specified in Section 8(a), the Company, on the one hand, and each Erin
                     ------------   
Mills Stockholder or Carlyle Stockholder, as applicable, on the other, (the
"Indemnifying Party"), will, subject to the limitations set forth in Section
- -------------------                                                  -------   
8(a), indemnify the Erin Mills Stockholders or the Carlyle Stockholders, on the
- ---
one hand, or the Company on the other, as the case may be (the "Indemnified
Party") against and in respect of all losses, damages, liabilities, costs, and
expenses (including reasonable attorneys' fees and expenses) incurred in
investigating, preparing or defending any claims covered by this Section 8(b)
                                                                 ------------
sustained or incurred arising out of any breaches by such Indemnifying Party of
its representations, warranties, covenants, and agreements set forth in this
Agreement. The indemnification provided for by this Section 8(b) will apply
                                                    ------------    
notwithstanding any investigation made by or on behalf of any party. Any
payments pursuant to this Section 8(b) will be treated as an adjustment to the
                          ------------
purchase price for all tax purposes.

                (c)     Method of Asserting Claims. In the event that an
                        --------------------------
Indemnified Party shall assert a claim for indemnity under this Section 8, (i)
                                                                ---------
the Indemnified Party will promptly after the receipt of notice of the
commencement of any action, investigation, claim, demand or other proceeding by
a third party against such Indemnified Party in respect of which indemnity may
be sought from any Indemnifying Party under this Section 8, notify the
Indemnifying Party in writing of the commencement thereof or (ii) if the claim
is other than such a third party claim, the Indemnified Party will notify the
Indemnifying Party promptly following its discovery of the facts or
circumstances giving rise thereto; provided, that in either case (i) or (ii), no
                                   --------
such notice need be provided by the Company to an Indemnifying Party who is a
Carlyle Stockholder or an Erin Mills Stockholder if the Carlyle Stockholder
Deductible or Erin Mills Stockholder Deductible, as applicable, has not been
exceeded and will not be exceeded by such claim or demand and the omission of
the Indemnified Party to so notify such Indemnifying Party of any such action
will not 

                                       8
<PAGE>
 
relieve such Indemnifying Party from any liability that it may have to such
Indemnified Party under this Section 8(c) unless, and only to the extent that,
                           ------------     
such omission prejudices the ability of the Indemnifying Party to defend such
action, investigation, claim, demand, or other proceeding or to reduce or
mitigate its liability under this Section 8, whether as a result of the
                                  ---------      
forfeiture of substantive rights or defenses or otherwise. In case any such
action, claim, or other proceeding is brought against the Indemnified Party such
Indemnified Party will notify the applicable Indemnifying Party of the
commencement thereof, the Indemnifying Party will be entitled to assume the
defense thereof at its own expense, with counsel satisfactory to such
Indemnified Party in its reasonable judgment, provided that the Deductible has
                                              --------  
been or will be exceeded, provided, further, that the Indemnified Party may, at
                          --------  --------       
its own expense, retain separate counsel to participate in such defense.
Notwithstanding the foregoing, in any action, claim or proceeding in which both
the Indemnifying Party, on the one hand, and an Indemnified Party, on the other
hand, is, or is reasonably likely to become, a party, such Indemnified Party
shall have the night to employ separate counsel at the Indemnifying Party's
expense and to control its own defense of such action, claim or proceeding if,
in the reasonable opinion of counsel to such Indemnified Party, a conflict or
potential conflict exists between the Indemnifying Party, on the one hand, and
such Indemnified Party, on the other hand, that would prevent the representation
of the Indemnified Party by counsel selected by and subject to the control of
the Indemnifying Party under applicable law or codes of professional
responsibility. Each of the Company, the Erin Mills Stockholders, and the
Carlyle Stockholders agrees that it will not, without the prior written consent
of the Indemnified Party, settle, compromise, or consent to the entry of any
judgment in any pending or threatened claim, action, or proceeding relating to
the matters contemplated by this Section 8 (if the Indemnified Party is a party
                                 ---------
thereto or has been actually threatened to be made a party thereto) unless such
settlement, compromise, or consent includes an unconditional release of the
Indemnified Party from all liability arising or that may arise out of such
claim, action or proceeding.

        SECTION 9.      Covenants.
                        ---------

                (a)     Inspection Rights. The Company will permit, and cause
                        -----------------
its subsidiaries to permit, the representatives designated by the Erin Mills
Stockholders and the Carlyle Stockholders so long as (i) the Erin Mills
Stockholders and the Carlyle Stockholders and their affiliates together
beneficially own 1,600,000 shares of Common Stock or (ii) the representation and
warranties of the Company set forth in this Agreement survive, upon reasonable
notice and during normal business hours, to (x) visit and inspect any of the
properties of the Company and its subsidiaries, (y) examine the corporate and
financial records of the Company and its subsidiaries and to make copies
thereof, and (z) discuss the affairs, finances and accounts of any such entities
with the directors, officers, key employees, and (with the prior consent of the
Company, which will not be unreasonably withheld) independent accountants of the
Company and its subsidiaries.

                (b)     Confidentiality. Each of the Erin Mills Stockholders and
                        ---------------
the Carlyle Stockholders will hold in confidence all information and data
obtained by it from the Company or its subsidiaries (whether in connection with
the negotiation of the transactions contemplated by this Agreement, pursuant to
Section 9(a) or otherwise) and will not disclose such information to any person
- -----------
or entity without the prior written consent of the Company (except that the Erin
Mills Stockholders and the Carlyle Stockholders may disclose such information to
their affiliates, 

                                       9
<PAGE>
     
directors, officers, and other representatives who require access to such
information in order to enable them to exercise their rights under this
Agreement or for any other proper purpose contemplated thereby and who agree to
be subject to the restrictions set forth in this Section 9(b), provided,
                                                 -----------   --------
however, that the provisions of this Section 9(b) will not apply to any
- -------                              -----------           
information or data that can be shown (i) to be generally available to the
public through no fault of such party or its affiliates, directors, officers,
and other representatives or (ii) to have been lawfully obtained by the Erin
Mills Stockholders or the Carlyle Stockholders from other sources not subject to
a confidentiality obligation to the Company     
    
      SECTION 10.    Applicable Law. This Agreement will be governed by and
                     ---------------
construed ice with the laws of the State of Delaware, without regard to any
conflicts of law principles that would require the application of the laws of
any other jurisdiction.     
    
      SECTION 11.    Parties in Interest; Assignment. This Agreement will be
                     -------------------------------
binding on and will inure to the benefit of the parties to this Agreement and
their respective successors and permitted assigns. No party may assign this
Agreement or its rights and benefits under this Agreement or delegate and duties
under this Agreement to any other person or entity without the prior written
consent of the other parties.     
    
      SECTION 12.    Amendment; Waiver. The provisions of this Agreement may be
                     ----------------- 
amended only by a written instrument executed by each of parties to this
Agreement, and compliance with the provisions of this Agreement may be waived
only by a written instrument executed by each party entitled to the benefits of
such provision. No failure on the part of any party to exercise any right,
power, or privilege granted under this Agreement will operate as a waiver of
such right, power, or privileges nor will any single exercise of such right,
power, or privilege preclude any other or further exercise or party of such
right, power, or privilege or the exercise of any other night, power or
privilege granted under this Agreement.     
    
      SECTION 13.    Further Assurances. Each party agrees to do, or cause to be
                     ------------------
done, such further acts and to execute and deliver, or to cause to be executed
and delivered, such further agreements, instruments, certificates, and other
documents as may be necessary or appropriate to effectuate and carry out the
purposes of this Agreement.     
    
      SECTION 14. Notices and Other Communications. All notices and other
                  --------------------------------
communications under this Agreement will be in writing and will be given by
delivery in person, by registered or certified mail (return receipt requested
and with postage prepaid thereon) or by cable, telex or facsimile transmission
to the parties at the following addresses (or at such other address as either
party will have furnished to the other in accordance with the terms of this
Section 14):
- ----------      

                                       10
<PAGE>
 
if to the Company, to:

HighwayMaster Communications, Inc.
16479 Dallas Parkway
Suite 710
Dallas, Texas 75248
Attention:  William C Kennedy, Jr.

if to any of the Erin Mills Stockholders, to:

Erin Mills International Investment Corporation
Trident House, Suite 204(a)
Broad Street
Bridgetown, Barbados
West Indies
Attention:  Stephen Greaves

if to any of the Carlyle Stockholders (except for the
Carlyle Stockholders that are Clipper
Stockholders (as defined in the 
Stockholders' Agreement)), to:

The Carlyle Group, L.P.
1001 Pennsylvania Avenue
Suite 220 South
Washington, D.C. 20004-2505
Attention:  Mark D. Ein

if to any Clipper Stockholders, to:

The Clipper Group, L.P
12 East 49th Street
New York, New York 10017
Attention:  Daniel V. Cahillane

All notices and other communications under this Agreement that are addressed as
provided in or pursuant to this Section 14 will be deemed duly and validly given
                                ----------
(a) if delivered in person, upon delivery, (b) if delivered by registered or
certified mail (return receipt requested and with postage paid thereon), 72
hours after being placed in a depository of the United States mails, and (c) if
delivered by cable, telex, or facsimile transmission, upon transmission thereof
and receipt of the appropriate answer back.

                SECTION 15.     Entire Agreement.  This Agreement constitutes
                                ----------------  
the entire agreement and understanding of the parties to this Agreement with
respect to the subject matter of this Agreement and supersedes any prior or
contemporaneous oral and prior written agreements or understandings between the
parties with respect to the subject matter of this Agreement.

                                       11
<PAGE>
 
                SECTION 16.     Headings.  The section headings contained in
                                --------
this Agreement are inserted for the convenience of reference only and are not
intended to be a part of or to affect the meaning or interpretation of this
Agreement.

                SECTION 17.     Counterparts.  This Agreement may be executed in
                                ------------
one or more counterparts, each of which will be deemed an original and all of
which together will constitute one and the same instrument.

                SECTION 18.     No Group or Beneficial Ownership.  Nothing in
                                --------------------------------
this Agreement will be deemed to constitute any party to this Agreement as
member of a "group" for the purposes of the Securities Exchange Act of 1934, as
amended, or to be an admission that any party to this Agreement beneficially
owns any of the securities of any other party to this Agreement.

                SECTION 19.     Expenses.  The Company will (i) reimburse each
                                --------
of the Carlyle Stockholders and the Erin Mills Stockholders for stamp and other
stock issuance or similar taxes that may be payable in respect of the execution
and delivery of this Agreement or the issuance, delivery, or acquisition of any
shares of Common Stock to be issued under this Agreement (but excluding any
income or similar state of federal taxes). Except as otherwise expressly
provided in this Agreement, the parties will bear their own respective expenses
(including, but not limited to, all compensation and expenses of counsel,
financial advisors, consultants, actuaries, and independent accountants)
incurred in connection with this Agreement and the transactions contemplated by
this Agreement or the Investment Documents.

                SECTION 20.     Limitation on Company Representations.  
                                -------------------------------------
Notwithstanding any provision of this Agreement to the contrary, the Company
makes no representation or warranty, and will have no obligation to indemnify or
liability for damages for, any matter to the extent that the material facts with
respect to such matter are known to any Carlyle Stockholders or Erin Mills
Stockholders as of the date of this Agreement.

                    [REMAINDER OF PAGE INTENTIONALLY BLANK]

                                       12
<PAGE>
 
                  IN WITNESS WHEREOF, the parties to this Agreement have caused
this Agreement to be duly executed as of the date first above written.

                                 HIGHWAYMASTER COMMUNICATIONS, INC.

                                 By:   _____________________________
                                                                    
                                 Name: _____________________________
                                                                    
                                 Title:_____________________________ 

                                 CLIPPER CAPITAL ASSOCIATES, L.P.
                                 By:      CLIPPER CAPITAL ASSOCIATES, INC.

                                 Its: General Partner

                                      By:    ________________________
                                                                     
                                      Name:  ________________________
                                     
                                      Title: ________________________


                                 CLIPPER/MERBAN, L.P.

                                 By: CLIPPER CAPITAL ASSOCIATES, L.P.
                                     --------------------------------

                                 Its General Partner

                                      By:    CLIPPER CAPITAL ASSOCIATES
                                      
                                      Its:   General Partner

                                      By:    ________________________
                                                                     
                                      Name:  ________________________
                                     
                                      Title: ________________________

                                 CLIPPER/MERCHANT PARTNERS, L.P.

                                 By:    CLIPPER CAPITAL ASSOCIATES, 
                                             L.P.
                                 Its:   General Partner

                                      By:    ________________________
                                                                     
                                      Name:  ________________________
                                     
                                      Title: ________________________

                                       13
<PAGE>

                                 By:  T.C. GROUP, L.L.C.
                                 Its: General Partner  

                                      By:
                                         ----------------------------
                                      Name: 
                                            -------------------------
                                      Title: 
                                             ------------------------ 
                                     
 
                                 CARLYLE-HIGHWAYMASTER INVESTORS II, 
                                 L.P.

                                 By:    T.C. GROUP, L.L.C.
                                 Its:   General Partner

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


                                 CHASE MANHATTAN INVESTMENT 
                                 HOLDINGS, INC.
 
                                 By:    
                                    ---------------------------------
                                 Name:  
                                      -------------------------------
                                 Title:
                                      -------------------------------

                                 H.M. RANA INVESTMENTS LIMITED

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

                                ARCHERY PARTNERS

                                By:
                                     ----------------------------------
                                Its:  General Partner

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

                                 THE ERIN MILLS INVESTMENT 
                                 CORPORATION

                                       14
<PAGE>
 
                                 By:    
                                        -----------------------------
                                 Name:  
                                        -----------------------------
                                 Title  
                                        -----------------------------


                                 THE ERIN MILLS DEVELOPMENT 
                                 CORPORATION

                                 By:    
                                        -----------------------------
                                 Name:  
                                        -----------------------------
                                 Title  
                                        -----------------------------
                                 
                                 ERIN MILLS INTERNATIONAL INVESTMENT 
                                 CORPORATION

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


                                 ------------------------------------
                                 Robert T. Hayes


                                 ------------------------------------
                                 Robert S. Folsom

                                       15
<PAGE>
 
                                                                EXHIBIT A

1.       Carlyle Stockholders
         --------------------

         Clipper Capital Associates, L.P.
         Clipper/Merban, L.P.
         Clipper/Merchant Partners, L.P.
         Carlyle-HighwayMaster Investors, L.P.
         Carlyle-HighwayMaster Investors II, L.P.
         Chase Manhattan Investment Holdings, Inc.
         H.M. Rana Investments Limited
         Archery Partners

2.       Erin Mills Stockholders
         -----------------------
       
         The Erin Mills Investment Corporation
         The Erin Mills Development Corporation
         Erin Mills International Investment Corporation
         Robert T. Hayes
         Robert S. Folsom

                                       16
<PAGE>
 
                                                                 EXHIBIT B


<TABLE> 
<CAPTION> 

                                                                                     Number of Shares of Series B 
                                         Number of Shares of B Stock                     Preferred Stock to be
                                               to be Received                                  Surrendered
         Name                   
<S>                                      <C>                                         <C> 
The Erin Mills Development 
Corporation                                        743,284                                       929.105
                                                   
Robert T. Hayes                                     86,436                                       108.0450
                                                   
Robert S. Folsom                                    34,280                                        42.85
                                                   -------                                      ----------
                                                   
         Totals                                    864,000                                         1.080
                                                   =======                                      ==========


</TABLE> 

                                       17
<PAGE>
 
                                                                    EXHIBIT C
                                                          
Name                                                  Excluded Interest
                                                    
Clipper Capital Associates, L.P.                        $   148.96
Clipper/Merban, L.P.                                      8,396.97
Clipper/Merchant Partners, L.P.                           8,290.78
Carlyle-HighwayMaster Investors, L.P.                    25,866.62
Carlyle-HighwayMaster Investors II, L.P.                  2,436.33
Chase Manhattan Investment Holdings, Inc.                 6,191.77
H.M. Rana Investments Limited                            10,522.67
Archery Partners                                          1,282.93
                                                        ----------
                                                        $63,137.03
                                                        ==========

                                       18

<PAGE>


              ==================================================== 
                       HIGHWAYMASTER COMMUNICATIONS, INC.

                              AMENDED AND RESTATED
                            STOCKHOLDERS' AGREEMENT

                                  Dated as of

                               September 27, 1996
              ====================================================

                                        
<PAGE>
 
                               TABLE OF CONTENTS

                  AMENDED AND RESTATED STOCKHOLDERS' AGREEMENT


                                                                            Page
<TABLE>
<CAPTION>
 
 
<S>               <C>                                                        <C>
Section 1.        Definitions................................................  2
             
Section 2.        The Recapitalization; Amendment of Certificate
                  of Incorporation...........................................  6
             
Section 3.        Transfer of Securities.....................................  7
             
Section 4.        Registration Rights........................................ 10
             
Section 5.        Governance................................................. 28
             
Section 6.        Miscellaneous.............................................. 35
</TABLE>

                                      ii
<PAGE>
 
                              AMENDED AND RESTATED
                            STOCKHOLDERS' AGREEMENT

          This AMENDED AND RESTATED STOCKHOLDERS' AGREEMENT ("Agreement"), dated
                                                              ---------         
as of September 27, 1996, amends and restates in its entirety that Stockholders'
Agreement, dated as of February 4, 1994 (the "Original Agreement"), by and among
HIGHWAYMASTER COMMUNICATIONS, INC., a Delaware corporation (previously named HM
HOLDING CORPORATION) (the "Company"), and the other Persons (as hereinafter
                           -------                                         
defined) identified in Appendix A hereto, as the Original Agreement has been
amended by the amendments and addenda set forth in Appendix B hereto, adds an
additional party hereto, Southwestern Bell Wireless Holdings, Inc., a Delaware
corporation ("SBW") and provides that the Persons identified in Appendix C
hereto shall no longer be parties hereto.


                                   RECITALS:

          A.  Simultaneously with the execution hereof, SBW is acquiring certain
shares of Series D Preferred Stock (as hereinafter defined) of the Company
pursuant to the Purchase Agreement dated as of the date hereof, by and between
the Company and SBW (the "Purchase Agreement") and agreeing to provide certain
                          ------------------                                  
services to the Company pursuant to a separate technical services agreement.

          B.  Certain of the parties hereto have effected, or agreed to effect,
the Recapitalization reflected in Sections 2(a), (b) and (c) hereof.

          C.  Pursuant to Section 7(h) of the Original Agreement with respect to
the terms hereof generally and Section 4(k) of the Original Agreement with
respect to the registration rights provisions, holders of a sufficient number of
Shares (as hereinafter defined) have executed this Agreement thereby amending
and restating the Original Agreement, as amended to date, in its entirety as set
forth herein, for the purpose of regulating certain aspects of the Stockholders'
relationships with regard to each other and the Company.

          D.  Immediately after the execution hereof, the Stockholders (as
hereinafter defined) will consist of (i) Carlyle HighwayMaster Investors, L.P.,
Carlyle HighwayMaster Investors II, L.P., H.M. Rana Investments Limited, TC
Group, L.L.C., Mark D. Ein, Chase Manhattan Investment Holdings, Inc. and
Archery Partners (the "Carlyle Entities"), (ii) Clipper/Merban, L.P.,
                       ----------------                              
Clipper/Merchant Partners, L.P. and Clipper

                                       1
<PAGE>
 
Capital Associates, L.P. (the "Clipper Entities"), (iii) Erin Mills
                               ----------------                    
International Investment Corporation, The Erin Mills Investment Corporation and
The Erin Mills Development Corporation (the "Erin Mills Companies"), 
                                             --------------------
(iv) William C. Kennedy, Jr., Donald M. Kennedy, William C. Saunders, Robert S.
Folsom and Robert T. Hayes and (v) SBW.

          E.  Simultaneously with the execution hereof, the Company is issuing
to SBW a warrant certificate for warrants (the "Warrants") for 5,000,000 shares
of Common Stock (as hereinafter defined) in consideration for SBW entering into
the transactions contemplated by the Purchase Agreement and the other
Transaction Documents (as hereinafter defined).

                                  AGREEMENT:

          NOW THEREFORE, in consideration of the mutual covenants herein
contained and for other good and valuable consideration, the Company and
Stockholders agree as follows:

           Section 1.  Definitions.  As used herein, the following terms shall
                       -----------                                            
have the following meanings:

          "Affiliate" of any specified person or entity means any person or
           ---------                                                       
entity directly or indirectly controlling or controlled by or under direct or
indirect common control with such person or entity.

          "Anti-takeover Provision" shall have the meaning set forth in Section
           -----------------------                                             
5(g) hereto.

          "Beneficially Own"  (and correlative terms) means, with respect to any
           ----------------                                                     
shares of Common Stock or other securities, to be entitled, directly or
indirectly through one or more intermediaries, to all material incidents of
ownership with respect to such securities, including, but not limited to, 
(i) the right to vote such securities (in the case of voting securities), 
(ii) subject to any transfer restrictions, the right to dispose of such
securities and to receive any proceeds realized from the disposition thereof and
(iii) the right to receive any dividends and other distributions with respect to
such securities.

          "By-Word Stockholder" means each of William C. Kennedy, Jr., Donald M.
           -------------------                                                  
Kennedy, William C. Saunders, Robert T. Hayes and Robert S. Folsom.

          "Carlyle Entities" shall have the meaning set forth in the Recitals
           ----------------                                                  
hereto.

                                       2
<PAGE>
 
          "Carlyle Stockholder" means each of the Carlyle Entities and any
           -------------------                                            
Permitted Assign (as hereinafter defined) who acquires shares of Common Stock
directly or indirectly from a Carlyle Stockholder and who executes a
supplemental agreement as contemplated in Section 6(b) hereof, in his, her or
its capacity as a holder of Common Stock.

          "Class B Common Stock" means the new class of Company Common Stock,
           --------------------                                              
par value $0.01 per share, to be authorized as contemplated in Section 2(e)
hereof, the terms of which are set forth on Exhibit B to the Purchase Agreement.

          "Clipper Entities" shall have the meaning set forth in the Recitals
           ----------------                                                  
hereto.

          "Clipper Stockholder" means each of the Clipper Entities.
           -------------------                                     

          "Commission" means the Securities and Exchange Commission.
           ----------                                               

          "Common Stock" means the Common Stock, par value $.01 per share, of
           ------------                                                      
the Company and any other capital stock of the Company into which such Common
Stock is reclassified or reconstituted.

          "Company Common Stock" means the Common Stock and the Class B Common
           --------------------                                               
Stock.

          "Demand Registration" shall have the meaning set forth in Section 4(b)
           -------------------                                                  
hereof.

          "Director" means a member of the Board of Directors of the Company.
           --------                                                          

          "Erin Mills Companies" shall have the meaning set forth in the
           --------------------                                         
Recitals hereto.

          "Erin Mills Stockholder" means each of the Erin Mills Companies and
           ----------------------                                            
any Permitted Assign who acquires shares of Common Stock directly or indirectly
from an Erin Mills Company and who executes a supplemental agreement as
contemplated in Section 6(b) hereof and, solely for purposes of Section 4
hereof, Robert S. Folsom and Robert T. Hayes, in each case in his, her or its
capacity as a holder of Common Stock.

          "Excluded Options" means options, warrants, rights or obligations to
           ----------------                                                   
acquire Common Stock issued by any Person other than the Company.

                                       3
<PAGE>
 
          "Excluded Related Party" means, with respect to any Stockholder, a
           ----------------------                                           
Related Party of such Stockholder which either (i) is a natural person or (ii)
is not an Affiliate of such Stockholder.

          "Exempt Transfer" shall mean the meaning set forth in Section 3(d)
           ---------------                                                  
hereof.

          "Existing Line of Business" shall have the meaning set forth in
           -------------------------                                     
Section 5(g) hereof.

          "Incentive Stock Option Plan" means the HM Holding Corporation 1994
           ---------------------------                                       
Incentive Stock Option Plan, as adopted by the Company's Board of Directors and
as amended from time to time, providing for the grant to certain management
employees of the Company and its Subsidiaries of options to purchase shares of
Common Stock.

          "Majority in Interest" means, with respect to any specified group of
           --------------------                                               
Stockholders, Stockholders included in such group which hold more than fifty
percent (50%) of the aggregate shares of Common Stock held collectively by such
group of Stockholders on a Fully Diluted Basis (as hereinafter defined).

          "On a Fully Diluted Basis" with respect to the Company's Common Stock
           ------------------------                                            
means on a basis that takes into account the number of shares of Common Stock
which are issued and outstanding plus the number of shares of Common Stock
issuable upon conversion of any outstanding Series D Preferred Stock and, once
authorized and issued, Class B Common Stock or pursuant to outstanding options,
warrants, rights or obligations to purchase or subscribe for shares of Common
Stock or securities of the Company which are exchangeable or exercisable into
shares of Common Stock as of the applicable date of determination, other than
the Warrants, Excluded Options and employee stock options.

          "Permitted Assign" shall have the meaning set forth in Section 6(b)
           ----------------                                                  
hereof.

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

          "Piggyback Registration" shall have the meaning set forth in Section
           ----------------------                                             
4(a) hereof.

                                       4
<PAGE>
 
          "Public Transferee" means any subsequent holder of Common Stock who
           -----------------                                                 
acquires Shares from a Stockholder pursuant to an effective registration
statement under the Securities Act (as hereinafter defined) or pursuant to Rule
144 promulgated thereunder.

          "Recapitalization Agreement" means the Recapitalization Agreement,
           --------------------------                                       
dated as of the date hereof, among the Company, certain Erin Mills Stockholders,
Carlyle Stockholders and Clipper Stockholders, a copy of which is attached as
Exhibit A hereto.

          "Recapitalization Shares" shall have the meaning set forth in Section
           -----------------------                                             
4(c) hereof.

          "Regulatory Relief" means that SBC Communications, Inc. or its
           -----------------                                            
Affiliates, in their sole judgment, have obtained all necessary federal and
state regulatory approvals to provide landline, interLATA long-distance service
pursuant to the Communications Act of 1934, as amended by The Telecommunications
Act of 1996.

          "Related Party"  with respect to any Stockholder means:  (A) an
           -------------                                                 
Affiliate of such Stockholder; (B) a trust, corporation, partnership or other
entity, the beneficiaries, stockholders, partners, or owners, or persons holding
a controlling interest of which consist of such Stockholder and/or its
Affiliates; (C) with respect to any Stockholder who is an individual, such
Stockholder's spouse, siblings, children or parents; (D) with respect to any
Stockholder which is a partnership, such Stockholders' partners as of the date
hereof; and (E) with respect to any Stockholder which is a corporation, such
Stockholder's stockholders as of the date hereof.

          "SBW Stockholder" means SBW and any Affiliate of SBW who acquires
           ---------------                                                 
Shares from SBW and who executes a supplemental agreement as contemplated in
Section 6(b) hereof.

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

          "Series D Preferred Stock" means the Series D Participating
           ------------------------                                  
Convertible Preferred Stock, par value $.01 per share, of the Company, the
Certificate of Designation for which is set forth in Exhibit A to the Purchase
Agreement.

          "Shares" means (i) any shares of the capital stock of the Company and
           ------                                                              
(ii) any securities convertible into, and any rights, options or warrants
exchangeable or

                                       5
<PAGE>
 
exercisable for, any of the shares of the capital stock of the Company, in
either case, at any time outstanding.

          "Stockholders" means the By-Word Stockholders, the Carlyle
           ------------                                             
Stockholders, the Clipper Stockholders, the Erin Mills Stockholders and the SBW
Stockholders.

          "Subsidiary" of any specified person or entity means a corporation or
           ----------                                                          
other entity of which a majority of the voting power of the equity securities or
other equity interests is owned, directly or indirectly, by such specified
person or entity or any Subsidiary of such specified person or entity.

          "Transaction Documents" shall have the meaning set forth in the
           ---------------------                                         
Purchase Agreement.

          "Transfer" shall have the meaning set forth in Section 3(a) hereof.
           --------                                                          
          "Warrants" shall have the meaning set forth in the Recitals hereto.
           --------                                                          

          Section 2.  The Recapitalization; Amendment of Certificate of
                      -------------------------------------------------
                      Incorporation.
                      ------------- 

          (a) Erin Mills Companies.
              -------------------- 

          (1) $10 Million Investment.  Simultaneously with the execution hereof,
              ----------------------                                            
     Erin Mills International Investment Corporation and one of its affiliates
     are  investing $10.0 million in cash in the Company in exchange for 800,000
     shares of Common Stock, as provided in the Recapitalization Agreement.

          (2) Series B Preferred Stock.  Simultaneously with the execution
              ------------------------                                    
     hereof, the Series B Preferred Stock owned by The Erin Mills Development
     Corporation and certain of its affiliates and by Robert S. Folsom and
     Robert T. Hayes is being exchanged for 864,000 shares of Common Stock, as
     provided in the Recapitalization Agreement.

          (b) Carlyle and Clipper Entities.  Simultaneously with the execution
              ----------------------------                                    
hereof, the promissory notes in the aggregate principal amount of approximately
$12.7 million held by certain Carlyle Stockholders and the Clipper Stockholders
together with accrued and unpaid interest in the amount of approximately
$63,000, which were issued by the Company pursuant to the Note Exchange and
Amendments Agreement, dated

                                       6
<PAGE>
 
as of May 26, 1995, are being converted into shares of Common Stock at a price
of $12.50 per share, as provided in the Recapitalization Agreement.

          (c) Termination of Subscription Agreement.  Simultaneously with the
              -------------------------------------                          
execution hereof, the Company, certain Carlyle Stockholders and the Clipper
Stockholders are terminating certain provisions of the Subscription Agreement,
dated as of February 4, 1994, as provided in the Recapitalization Agreement.

          (d) Bylaws.  Simultaneously with the execution hereof, the Company has
              ------                                                            
amended the Bylaws as set forth as Exhibit B hereto.

          (e) Amendment of Certificate of Incorporation.  The Stockholders
              -----------------------------------------                   
listed on Appendix D have granted written consents and irrevocable proxies to
SBW covering the shares of Common Stock owned by them with respect to the
amendment of the Certificate of Incorporation as set forth on Exhibit B to the
Purchase Agreement and the issuance of the Common Stock pursuant to the exercise
of the Warrants, and SBW has delivered to the Company written consents covering
such shares, and immediately following the issuance of the Series D Preferred
Stock, will deliver to the Company a written consent covering such shares, each
approving such amendment.  On the twentieth day following the mailing of an
information statement to the Company's stockholders in compliance with
Regulation 14C promulgated under the Securities Exchange Act of 1934, the
Company will cause the Certificate of Amendment to be filed with the Secretary
of State of the State of Delaware.

           Section 3.    Transfer of Securities
                         ----------------------

          (a) General Prohibition on Transfer.  None of the Stockholders shall
              -------------------------------                                 
     sell, assign, transfer, pledge, encumber or in any way dispose of
     ("Transfer") any Shares unless (i) such Stockholder shall have delivered to
     ----------                                                                 
     the Company an opinion of counsel to such Stockholder, in form and
     substance reasonably satisfactory to the Company, to the effect that such
     Transfer is exempt from the registration requirements of the Securities Act
     or (ii) the registration requirements of the Securities Act have been
     complied with in connection with such Transfer, provided, however, that the
     Company shall be entitled in its sole discretion to waive the requirement
     that an opinion of counsel be delivered pursuant to this Section 3(a) if it
     determines that a Transfer is in accordance with applicable law.

          (b) Transfer by First Refusal Stockholders.  None of the Carlyle
              --------------------------------------                      
     Stockholders, the Erin Mills Stockholders (other than Robert S. Folsom and

                                       7
<PAGE>
 
     Robert T. Hayes), William C. Kennedy, Jr. or William C. Saunders
     (collectively the "First Refusal Stockholders") shall Transfer any Shares
     unless (i) such First Refusal Stockholder has complied with the provisions
     of this Section 3(c) to the extent applicable to such Transfer and (ii) the
     transferee (if other than a Public Transferee or an Excluded Related Party)
     has agreed to become a party to, and be bound by the terms of, Section 3 of
     this Agreement pursuant to a supplemental agreement hereto in form and
     substance reasonably satisfactory to the Company and SBW, executed by such
     transferee (provided, however, that the requirement set forth in this
     clause (ii) shall not apply to any transferee (other than a Permitted
     Assign or a transferee pursuant to Section 3(d) who is not an Excluded
     Related Party) acquiring Shares from a Seller (as hereinafter defined)
     after the earlier of (A) the date of Regulatory Relief and (B) September
     27, 1997 pursuant to a sale effected by such Seller in compliance with the
     provisions of subsection (c) below).  Notwithstanding the foregoing, no
     First Refusal Stockholder shall be required to execute a supplemental
     agreement.

          (c)  Right of First Refusal.
               ---------------------- 

               (i) If any First Refusal Stockholder (a "Seller") receives a bona
                                                        ------                  
     fide offer, which the Seller desires to accept ("Offer") to purchase any or
     all of the Shares (the "Transfer Stock") then owned by such Seller from any
                             --------------                                     
     person (an "Offeror"), such Seller shall notify SBW in writing of the terms
     of such Offer, which notice shall identify the Offeror, the price offered,
     and all the other material terms and conditions of such Offer.  In
     addition, if a Seller wishes to sell to the public pursuant to a
     registration statement under the Securities Act or pursuant to Rule 144
     promulgated thereunder (a "Public Sale"), the Seller shall notify SBW in
     writing of the proposed terms of the Public Sale, which Public Sale shall
     also constitute an Offer for the purposes hereof.  The Seller shall provide
     a written notice (the "Notice") of an Offer to SBW promptly, but in no
                            ------                                         
     event later than five (5) business days following the determination by the
     Seller that it desires to accept an Offer which does not relate to a Public
     Sale.  The Notice shall contain an irrevocable offer to sell the Transfer
     Stock to SBW at a price equal to the price and upon substantially the same
     terms as the terms contained in such Offer; provided, however, that (A) if
     such Offer shall relate to a proposed Public Sale, the Notice shall offer
     to sell the Transfer Stock at a price determined by the Seller (which in
     the case of a registered public offering shall not be higher than the price
     the Seller in good faith

                                       8
<PAGE>
 
     believes can be obtained in such offering), minus, in the case of a
     registered public offering pursuant to a firm commitment underwriting,
     customary underwriting commissions, and (B) if the terms of the Offer
     entitle the Offeror to purchase the Transfer Stock for securities of such
     Offeror (the "Offered Securities") or other property, SBW shall be entitled
                   ------------------                                           
     to purchase the Transfer Stock for an amount of cash equal to the fair
     market value of the Offered Securities or such other property.  SBW shall
     have the irrevocable right and option (the "Right of First Refusal"), to
                                                 ----------------------      
     accept such irrevocable offer as to all Shares as to which the Offer is
     made (except in the event of a Public Sale pursuant to Rule 144, in which
     event SBW may accept as to any number of Shares) by providing the Seller
     with an irrevocable written notice of acceptance within fifteen (15)
     business days, or, in the case of a Public Sale pursuant to Rule 144, five
     (5) business days, after the date the Notice is received (the "Notice
                                                                    ------
     Period").  The closing of the purchases of the Transfer Stock by SBW shall
     ------                                                                    
     take place at the principal office of SBW no later than the fifth (5th)
     business day after the acceptance by SBW.  At such closing, SBW shall
     deliver a certified check or checks or wire transfer in the appropriate
     amount to the Seller against delivery of certificates representing the
     Transfer Stock so purchased, duly endorsed in blank by the person or
     persons in whose name a stock certificate is registered or accompanied by a
     duly executed assignment separate from the certificate with the signatures
     thereon guaranteed by a commercial bank or trust company.  If SBW does not
     elect to purchase the Transfer Stock during the Notice Period or if SBW
     fails or refuses for any reason (including, but not limited to, the
     existence of any requirement that SBW obtain any required regulatory
     approval) to complete the closing of the purchase of any Transfer Stock
     upon the day specified above, the Seller shall have ninety (90) days from
     the end of the Notice Period (the "Sales Period") in which to Transfer all
                                        ------------                           
     of the Transfer Stock pursuant to the Offer to the Offeror or in a Public
     Sale, it being understood that (A) in a registered public offering the
     sales price may be greater than or less than the Offer price and (B) in any
     other transaction the sales price and other terms of the Transfer may be
     more favorable to the Seller than those set forth in the Notice.  In
     addition, Seller may not knowingly make a Public Sale to any purchaser
     which Seller knows to own in excess of 5% of the Common Stock, provided
     that this restriction shall not create any duty of inquiry on the part of
     the Seller.  Promptly after any sale pursuant to this Section 3(c), the
     Seller shall notify SBW of the consummation thereof and shall furnish such
     evidence of the completion (including time of completion) of such sale

                                       9
<PAGE>
 
     and of the terms thereof as SBW may reasonably request.  If, at the
     termination of the Sales Period, the Seller has not completed the sale of
     the Transfer Stock to the Offeror or in a Public Sale, all of the
     restrictions on Transfer contained in this Section 3(c) shall again be in
     effect with respect to all such Seller's Transfer Stock.

          (d) Exempt Transfer.  The following transactions shall constitute
              ---------------                                              
     "Exempt Transfers" for the purpose of Section 3 and shall be exempt from
     -----------------                                                       
     the requirements of subsection (c), but not subsections (a) and (b):  (i) a
     Transfer of Shares by a First Refusal Stockholder to SBW, (ii) a Transfer
     by a Stockholder of Shares by will or intestate succession to such
     Stockholder's executors, administrators, testamentary trustees, legatees or
     beneficiaries, (iii) a Transfer of Shares by a Stockholder to any Related
     Party of such Stockholder and (iv) a Transfer of Shares (A) by any Carlyle
     Stockholder to any other Carlyle Stockholder or to any Clipper Stockholder,
     (B) by any Erin Mills Stockholder to any other Erin Mills Stockholder or
     (C) by William C. Kennedy, Jr. or William C. Saunders to any By-Word
     Stockholder, or (vi) a Transfer of Shares that has been approved in writing
     by SBW as an Exempt Transfer.

          (e) Restrictions on SBW.   No SBW Stockholder shall Transfer any
              -------------------                                         
     Series D Preferred Stock or Class B Common Stock except to an Affiliate of
     SBW.

           Section 4.    Registration Rights.
                         ------------------- 

          (a) Piggyback Registration Rights.
              ----------------------------- 

          (1) Right to Piggyback. Subject to the last sentence of this
              ------------------                                      
     subsection (1), whenever the Company proposes to register any shares of
     Common Stock (or securities convertible into or exchangeable for, or
     options, warrants or other rights to acquire, Common Stock) with the
     Securities and Exchange Commission (the "Commission") under the Securities
                                              ----------                       
     Act (other than (A) registrations on Form S-4 or Form S-8 and (B) the
     registration of the Recapitalization Shares (as hereinafter defined)
     pursuant to subsection (c) below) and the registration form to be used may
     be used for the registration of the Registrable Securities (as defined in
     subsection (k) below) (a "Piggyback Registration"), the Company will give
                               ----------------------                         
     written notice to all Stockholders, at least thirty-five (35) days prior to
     the

                                       10
<PAGE>
 
     anticipated filing date, of its intention to effect such a registration,
     which notice will specify the proposed offering price, the kind and number
     of securities proposed to be registered, the distribution arrangements and
     such other information that at the time would be appropriate to include in
     such notice, and will, subject to subsection (a)(2) below, include in such
     Piggyback Registration all Registrable Securities with respect to which the
     Company has received written requests for inclusion therein within fifteen
     (15) business days after the effectiveness of the Company's notice.  Except
     as may otherwise be provided in this Agreement, Registrable Securities with
     respect to which such request for registration has been timely received
     will be registered by the Company and offered to the public in a Piggyback
     Registration pursuant to this Section 4 on terms and conditions at least as
     favorable as those applicable to the registration of shares of Common Stock
     (or securities convertible into or exchangeable or exercisable for Common
     Stock) to be sold by the Company and by any other person selling under such
     Piggyback Registration.

          (2) Priority on Piggyback Registrations. If the managing underwriter
              -----------------------------------                             
     or underwriters, if any, advise the holders of Registrable Securities in
     writing that in its or their reasonable opinion or, in the case of a
     Piggyback Registration not being underwritten, the Company shall reasonably
     determine (and notify the holders of Registrable Securities of such
     determination), after consultation with an investment banker of nationally
     recognized standing, that the number or kind of securities proposed to be
     sold in such registration (including Registrable Securities to be included
     pursuant to subsection (a)(1) above) will materially adversely affect the
     success of such offering (including, without limitation, a material impact
     on the selling price), the Company will include in such registration the
     number of securities, if any, which, in the opinion of such underwriter or
     underwriters, or the Company, as the case may be, can be sold, without
     having a material adverse effect on the success of such offering, as
     follows: (i) first, the shares the Company proposes to sell, (ii) second,
     the Registrable Securities requested to be included in such registration by
     SBW, the Carlyle Stockholders, the Clipper Stockholders and the Erin Mills
     Stockholders, pro rata among such requesting Stockholders on the basis of
     their respective holdings of Common Stock on a Fully Diluted Basis, and
     (iii) third, the Registrable Securities requested to be included in such
     registration by the By-Word Stockholders, pro rata among such requesting

                                       11
<PAGE>
 
     Stockholders on the basis of their respective holdings of Common Stock on a
     Fully Diluted Basis.

          (3) Selection of Underwriters.  If any Piggyback Registration is an
              -------------------------                                      
     underwritten offering, the Company (by action of the Board of Directors)
     will select a managing underwriter or underwriters to administer the
     offering, which managing underwriter or underwriters will be of nationally
     recognized standing and reasonably acceptable to the holders of a majority
     of the Registrable Securities included therein.

          (b)  Demand Registration Rights.
               -------------------------- 

          (1) Right to Demand Registration.  Each of (A) the Carlyle
              ----------------------------                          
     Stockholders and the Clipper Stockholders as a group; (B) the Erin Mills
     Stockholders as a group and (C) SBW (each referred to herein as a
                                                                      
     "Demanding Group") shall have the right on the number of occasions set
     ----------------                                                      
     forth in subsection (b)(2) to make a written request of the Company for
     registration with the Commission, under and in accordance with the
     provisions of the Securities Act, of all or part of their Registrable
     Securities (a "Demand Registration"); provided, that (x) the Company shall
                    -------------------    --------                            
     not effect a Demand Registration unless such Demand Registration has been
     requested by persons holding at least a majority of the Registrable
     Securities held by the Demanding Group on the date of such written request
     and unless the number of Shares to be sold in such Demand Registration by
     the Demanding Group is at least 1,000,000 shares of Common Stock, (y) if
     the Board of Directors determines in the exercise of its reasonable
     judgment that, due to a pending or contemplated acquisition or disposition,
     to effect such Demand Registration at such time would have a material
     adverse effect on the Company, the Company may defer such Demand
     Registration for a single period not to exceed one hundred eighty (180)
     days (but if the Company elects to defer any Demand Registration pursuant
     to the terms of this sentence, no Demand Registration shall be deemed to
     have occurred for purposes of this Agreement) and (z) the Company shall be
     obligated to effect only the number of Demand Registrations set forth in
     subsection 4(b)(2) below.  Within ten (10) days after receipt of the
     request for a Demand Registration, the Company will send written notice
     (the "Notice") of such registration request and its intention to comply
           ------                                                           
     therewith to all Stockholders who are holders of Registrable Securities
     and, subject to subsection (3) below, the Company will include in such
     registration all

                                       12
<PAGE>
 
     Registrable Securities of such Stockholders with respect to which the
     Company has received written requests for inclusion therein within twenty
     (20) business days after the effectiveness of the Notice.  All requests
     made pursuant to this subsection (b)(1) will specify the aggregate number
     of Registrable Securities requested to be registered and will also specify
     the intended methods of disposition thereof.

          (2) Number of Demand Registrations.  Each Demanding Group shall be
              ------------------------------                                
     entitled to two (2) Demand Registrations, and the expenses of each
     (including the fees and expenses of a total of one counsel for the
     Demanding Group in accordance with subsection (f)(2) below) shall be borne
     by the Company.  A Demand Registration shall not be counted as a Demand
     Registration hereunder until such Demand Registration has been declared
     effective by the Commission and maintained continuously effective for a
     period of at least three months or such shorter period when all Registrable
     Securities included therein have been sold in accordance with such Demand
     Registration.

          If the Company elects to issue and sell and ultimately sells any
     equity securities pursuant to any Registration Statement filed in
     connection with a Demand Registration, then such Registration shall be
     deemed not to be a Demand Registration for purposes of determining the
     number of Demand Registrations granted by this Agreement.

          (3) Priority on Demand Registrations.  If in any Demand Registration
              --------------------------------                                
     the managing underwriter or underwriters thereof (or in the case of a
     Demand Registration not being underwritten, the holders of a majority of
     the Registrable Securities held by the Demanding Group after consultation
     with an investment banker of nationally recognized standing), advise the
     Company in writing that in its or their reasonable opinion the number of
     securities proposed to be sold in such Demand Registration exceeds the
     number that can be sold in such offering without having a material adverse
     effect on the success of the offering (including, without limitation, an
     impact on the selling price), the Company will include in such registration
     only the number of securities that, in the reasonable opinion of such
     underwriter or underwriters (or such holders of Registrable Securities held
     by the Demanding Group, as the case may be) can be sold without having a
     material adverse effect on the success of the offering, as follows: (i)
     first, the Registrable Securities requested to be included in such Demand

                                       13
<PAGE>
 
     Registration by the Demanding Group, pro rata, among such Stockholders on
     the basis of their respective holdings of Common Stock on a Fully Diluted
     Basis, (ii) second, the Registrable Securities requested to be included in
     such Demand Registration by the Erin Mills Stockholders and SBW (if the
     Demanding Group is the Carlyle Stockholders and the Clipper Stockholders),
     or the Carlyle Stockholders and the Clipper Stockholders, as a group, and
     SBW (if the Demanding Group is the Erin Mills Stockholders), or the Carlyle
     Stockholders and the Clipper Stockholders, as a group, and the Erin Mills
     Stockholders (if the Demanding Group is SBW), in all such cases pro rata
     among such Stockholders on the basis of their respective holdings of Common
     Stock on a Fully Diluted Basis, (iii) third, shares to be issued and sold
     by the Company and requested to be included in such Demand Registration,
     and (iv) fourth, the Registrable Securities requested to be included in
     such Demand Registration by the By-Word Stockholders, pro rata among such
     requesting Stockholders on the basis of their respective holdings of Common
     Stock on a Fully Diluted Basis.

          (4) Selection of Underwriters.  If a Demand Registration is an
              -------------------------                                 
     underwritten offering, the holders of a majority of the Registrable
     Securities to be included in such Demand Registration held by members of
     the Demanding Group that initiated such Demand Registration will select a
     managing underwriter or underwriters of recognized national standing to
     administer the offering, which managing underwriter or underwriters shall
     be reasonably acceptable to the Company.

          (c) Registration of Recapitalization Shares.  Within a reasonable
              ---------------------------------------                      
period prior to each Registration Date (as hereinafter defined), the Company
shall prepare and file with the Commission a registration statement on an
appropriate form in order to register the Recapitalization Shares under the
Securities Act for sale in one or more privately negotiated transactions or in
open market transactions effected on any stock exchange on which the Common
Stock is then listed, or if not so listed, on any automated quotation system to
which the Common Stock is then admitted to trading; provided, however, that if
the Board of Directors determines in the exercise of its reasonable judgment
that, due to a pending or contemplated acquisition or disposition, to effect
such registration at such time would have a material adverse effect on the
Company, the Company may defer such registration for a single period not to
exceed ninety (90) days.  The Company shall use its reasonable best efforts to
have each such registration statement declared effective by the Commission as
promptly as reasonably practicable after the filing thereof with the Commission;
provided, however, that (i) no sales of Recapitalization Shares shall be

                                       14
<PAGE>
 
effected pursuant to any such registration statement prior to March 31, 1997 and
(ii) sales of an aggregate of no more than one-half of the total number of
Recapitalization Shares shall be effected pursuant to any such registration
statement prior to September 27, 1997, such dates being referred to as the
"Registration Dates".  In addition, the Company shall use its reasonable best
efforts to keep such registration statement effective for a period of at least
three months after the applicable Registration Date.  As used herein, the term
"Recapitalization Shares" shall mean the shares of Common Stock issued pursuant
to the Recapitalization Agreement to Erin Mills International Investment
Corporation as described in Section 2(a)(1) hereof and to certain Carlyle
Stockholders and Clipper Stockholders as described in Section 2(b) hereof.

          (d)   Registration Procedures.  With respect to any Piggyback
                -----------------------                                
Registration or Demand Registration and (except as expressly provided in
subsection (c) above) the registration to be effected pursuant to subsection (c)
above (generically, a "Registration"), the Company will, subject to subsections
                       ------------                                            
4(a)(2) and 4(b)(3), as expeditiously as practicable:

          (1)   prepare and file with the Commission, within 60 days after
     mailing the applicable Notice, a registration statement or registration
     statements (the "Registration Statement") relating to the applicable
                      ----------------------
     Registration on any appropriate form under the Securities Act, which form
     shall be available for the sale of the Registrable Securities in accordance
     with the intended method or methods of distribution thereof; provided that
     the Company will include in any Registration Statement on a form other than
     Form S-1 all information that the holders of the Registrable Securities so
     to be registered shall reasonably request and shall include all financial
     statements required by the Commission to be filed therewith, cooperate and
     assist in any filings required to be made with the National Association of
     Securities Dealers, Inc. ("NASD") or any securities exchange on which the
                                ----                                          
     Common Stock may then be listed, and use its reasonable best efforts to
     cause such Registration Statement to become effective promptly; provided,
                                                                     -------- 
     further, that before filing a Registration Statement or prospectus related
     -------                                                                   
     thereto (a "Prospectus") or any amendments or supplements thereto, the
                 ----------                                                
     Company will furnish to the holders of the Registrable Securities covered
     by such Registration Statement and the underwriters, if any, copies of all
     such documents proposed to be filed, which documents will be subject to the
     reasonable review of such holders and underwriters and their respective
     counsel, and the Company will not file any Registration Statement or
     amendment thereto or any Prospectus or any supplement thereto to which

                                       15
<PAGE>
 
     the holders of a majority of the Registrable Securities covered by such
     Registration Statement, the Demanding Group, if a Demand Registration, or
     the underwriters, if any, shall reasonably object;

          (2)   prepare and file with the Commission such amendments and post-
     effective amendments to the Registration Statement as may be necessary to
     keep each Registration Statement effective for the applicable period, or
     such shorter period which will terminate when all Registrable Securities
     covered by such Registration Statement have been sold; cause each
     Prospectus to be supplemented by any required Prospectus supplement, and as
     so supplemented to be filed pursuant to Rule 424 under the Securities Act;
     and comply with the provisions of the Securities Act with respect to the
     disposition of all securities covered by such Registration Statement during
     the applicable period in accordance with the intended method or methods of
     distribution by the sellers thereof set forth in such Registration
     Statement or supplement to the Prospectus, provided, that the Company shall
                                                --------                        
     not be deemed to have used its reasonable best efforts to keep a
     Registration Statement effective during the applicable period if it
     voluntarily takes any action that would result in selling holders of the
     Registrable Securities covered thereby not being able to sell such
     Registrable Securities during that period unless such action is required
     under applicable law, and provided, further that the foregoing shall not
                               --------  -------                             
     apply to actions taken by the Company in good faith and for valid business
     reasons, including without limitation the acquisition or divestiture of
     assets, so long as the Company promptly thereafter complies with the
     requirements of subsection (11) of this subsection (d), if applicable;

          (3)   notify the selling holders of Registrable Securities and the
     managing underwriters, if any, promptly, and (if requested by any such
     person or entity) confirm such advice in writing, (A) when the Prospectus
     or any Prospectus supplement or post-effective amendment has been filed,
     and, with respect to the Registration Statement or any post-effective
     amendment, when the same has become effective, (B) of any request by the
     Commission for amendments or supplements to the Registration Statement or
     the Prospectus or for additional information, (C) of the issuance by the
     Commission of any stop order suspending the effectiveness of the
     Registration Statement or the initiation of any proceedings for that
     purpose, (D) if at any time the representations and warranties of the
     Company contemplated by subsection (14) below cease to be true and correct,
     (E) of

                                       16
<PAGE>
 
     the receipt by the Company of any notification with respect to the
     suspension of the qualification of the Registrable Securities for sale in
     any jurisdiction or the initiation or threatening of any proceeding for
     such purpose, (F) of any other correspondence from the Commission with
     respect to the Registration and (G) of the happening of any event which
     makes any statement made in the Registration Statement, the Prospectus or
     any document incorporated therein by reference untrue in any material
     respect or which requires the making of any changes in the Registration
     Statement, the Prospectus or any document incorporated therein by reference
     in order to make the statements therein not materially misleading;

          (4)   make every reasonable effort to obtain the withdrawal of any
     order suspending the effectiveness of the Registration Statement at the
     earliest possible moment;

          (5)   if requested by the managing underwriter or underwriters or a
     holder of Registrable Securities being sold in connection with an
     underwritten offering, promptly incorporate in a Prospectus supplement or
     post-effective amendment such information as the managing underwriters and
     either the holders of a majority of the Registrable Securities being sold
     or the Demanding Group, if a Demand Registration, agree should be included
     therein relating to the plan of distribution with respect to such
     Registrable Securities, including, without limitation, information with
     respect to the number of Registrable Securities being sold to such
     underwriters the purchase price being paid therefor by such underwriters
     and with respect to any other terms of the underwritten (or best efforts
     underwritten) offering of the Registrable Securities to be sold in such
     offering; and make all required filings of such Prospectus supplement or
     post-effective amendment promptly following notification of the matters to
     be incorporated in such Prospectus supplement or post-effective amendment;

          (6)   furnish to each selling holder of Registrable securities and
     each managing underwriter, without charge, at least one signed copy of the
     Registration Statement and any amendment thereto, including financial
     statements and schedules, all documents incorporated therein by reference
     and all exhibits (including those incorporated by reference);

                                       17
<PAGE>
 
          (7)   deliver to each selling holder of Registrable Securities and the
     underwriters, if any, without charge, as many copies of the Prospectus
     (including each preliminary prospectus) and any amendment or supplement
     thereto as such selling holder of Registrable Securities and underwriters
     may reasonably request; the Company consents to the use in accordance with
     applicable law of each Prospectus or any amendment or supplement thereto by
     each of the selling holders of Registrable Securities and the underwriters,
     if any, in connection with the offering and sale of the Registrable
     Securities covered by such Prospectus or any amendment or supplement
     thereto;

          (8)   prior to any public offering of Registrable Securities, register
     or qualify or cooperate with the selling holders of Registrable Securities,
     the underwriters, if any, and their respective counsel in connection with
     the registration or qualification of such Registrable Securities for offer
     and sale under the securities or "blue sky" laws of such jurisdictions as
     any seller or underwriter reasonably requests in writing, considering the
     amount of Registrable Securities proposed to be sold in each such
     jurisdiction, and do any and all other acts or things necessary or
     reasonably advisable to enable the disposition in such jurisdictions of the
     Registrable Securities covered by the Registration Statement; provided that
                                                                   --------     
     the Company will not be required to qualify generally to do business in any
     jurisdiction where it is not then so qualified or to take any action that
     would subject it to general service of process in any such jurisdiction
     where it is not then so subject;

          (9)   cooperate in all reasonable respects with the selling holders of
     Registrable Securities and the managing underwriters, if any, to facilitate
     the timely preparation and delivery of certificates representing
     Registrable Securities to be sold and not bearing any restrictive legends
     and to be in such denominations and registered in such names as the
     managing underwriters may request at least two business days prior to any
     sale of Registrable Securities to the underwriters;

          (10)  use its reasonable best efforts to cause the Registrable
     Securities covered by the applicable Registration Statement to be
     registered with or approved by such other governmental agencies or
     authorities as may be necessary to enable the seller or sellers thereof or
     the underwriters, if any, to consummate the disposition of such Registrable
     Securities;

                                       18
<PAGE>
 
          (11)  upon the occurrence of any event contemplated by subsection
     (3)(F) above, prepare a supplement or post effective amendment to the
     Registration Statement or the related Prospectus or any document
     incorporated therein by reference or file any other required document so
     that, as thereafter delivered to the purchasers of the Registrable
     Securities, the Prospectus will not contain an untrue statement of a
     material fact or omit to state any material fact necessary to make the
     statements therein not misleading;

          (12)  cause all Registrable Securities covered by any Registration
     Statement to be listed on each securities exchange on which similar
     securities issued by the Company are then listed, or cause such Registrable
     Securities to be authorized for trading on the Nasdaq National Market if
     any similar securities issued by the Company are then so authorized, if
     requested by the holders of a majority of such Registrable Securities, the
     Demanding Group, if a Demand Registration, or the managing underwriters, if
     any;

          (13)  provide a CUSIP number for all Registrable Securities, not later
     than the effective date of the applicable Registration Statement;

          (14)  enter into such agreements (including an underwriting agreement)
     and take all such other actions in connection therewith in order to
     expedite or facilitate the disposition of such Registrable Securities and
     in such connection, whether or not an underwriting agreement is entered
     into and whether or not the Registration is an underwritten Registration
     (A) make such representations and warranties to the holders of such
     Registrable Securities and the underwriters, if any, in form, substance and
     scope as are customarily made by issuers to underwriters in primary
     underwritten offerings; (B) obtain opinions of counsel to the Company and
     updates thereof (which counsel and opinions (in form, scope and substance)
     shall be reasonably satisfactory to the managing underwriters, if any, and
     the holders of a majority of the Registrable Securities being sold)
     addressed to each selling holder and the underwriters, if any, covering the
     matters customarily covered in opinions requested in underwritten offerings
     and such other matters as may be reasonably requested by such holders and
     underwriters; (C) obtain "cold comfort" letters and updates thereof from
     the Company's independent certified public accountants addressed to the
     selling holders of Registrable Securities and the underwriters, if any,
     such

                                       19
<PAGE>
 
     letters to be in customary form and covering matters of the type
     customarily covered in "cold comfort" letters by underwriters in connection
     with primary underwritten offerings; (D) if an underwriting agreement is
     entered into, the same shall set forth in full the indemnification
     provisions and procedures set forth in subsection (f) below with respect to
     all parties to be indemnified pursuant to said subsection; and (E) the
     Company shall deliver such documents and certificates as may be requested
     by the holders of a majority of the Registrable Securities being sold and
     the managing underwriters, if any, to evidence compliance with subsection
     3(G) of this subsection (d) and with any customary conditions contained in
     the underwriting agreement or other agreement entered into by the Company.
     The above shall be done at each closing under such underwriting or similar
     agreement or as and to the extent required thereunder;

          (15)  make available (at reasonable times and places) for inspection
     by a representative of the holders of a majority of the Registrable
     Securities, any underwriter participating in any disposition pursuant to
     such Registration, and any attorney or accountant retained by the sellers
     or underwriter, all financial and other records, pertinent corporate
     documents and properties of the Company, and cause the Company's officers,
     directors and employees to supply all information reasonably requested by
     any such representative, underwriter, attorney or accountant in connection
     with such Registration Statement; provided, that any records, information
                                       --------                               
     or documents that are designated by the company in writing as confidential
     shall be kept confidential by such Persons unless disclosure of such
     records, information or documents is required by court or administrative
     order or any regulatory body having jurisdiction;

          (16)  otherwise use its reasonable best efforts to comply with all
     applicable rules and regulations of the Commission, and make generally
     available to its security holders, earnings statements satisfying the
     provisions of Section 11(a) of the Securities Act, no later than forty-five
     (45) days after the end of any twelve (12)-month period (or ninety (90)
     days, if such period is a fiscal year) (A) commencing at the end of any
     fiscal quarter in which Registrable Securities are sold to underwriters in
     a firm or best efforts underwritten offering, or (B) if not sold to
     underwriters in such an offering, beginning with the first month of the
     Company's first fiscal quarter commencing after the effective date of the
     Registration Statement, which statements shall cover said twelve (12)-month
     periods; and

                                       20
<PAGE>
 
          (17)  promptly prior to the filing of any document that is to be
     incorporated by reference into any Registration Statement or Prospectus
     (after initial filing of the Registration Statement), provide copies of
     such document to counsel to the selling holders of Registrable Securities
     and to the managing underwriters, if any, make the Company's
     representatives available for discussion of such document and make such
     changes in such document prior to the filing thereof as counsel for such
     selling holders or underwriters may reasonably request.

          The Company may require each seller of Registrable Securities as to
     which any Registration is being effected to furnish to the Company such
     information regarding the proposed distribution of such securities as the
     Company may from time to time reasonably request in writing.

          Each holder of Registrable Securities agrees by acquisition of such
     Registrable Securities that, upon receipt of any notice from the Company of
     the happening of any event of the kind described in subsection (3)(G) of
     this subsection (d), such holder will forthwith discontinue disposition of
     Registrable Securities pursuant to the Registration Statement until such
     holder's receipt of copies of the supplemented or amended Prospectus as
     contemplated by subsection (11) of this subsection (d), or until it is
     advised in writing (the "Advice") by the Company that the use of the
                              ------                                     
     Prospectus may be resumed, and has received copies of any additional or
     supplemental filings that are incorporated by reference in the Prospectus,
     and, if so directed by the Company, such holder will deliver to the Company
     (at the Company's expense) all copies, other than permanent file copies
     then in such holder's possession, of the Prospectus covering such
     Registrable Securities current at the time of receipt of such notice.  In
     the event the Company shall give any such notice, the time periods referred
     to in subsection (2) of this subsection (d) shall be extended by the number
     of days during the period from and including the date of the giving of such
     notice to and including the date when each seller of Registrable Securities
     covered by such Registration Statement shall have received the copies of
     the supplemented or amended prospectus contemplated by subsection (11) of
     this subsection (d) or the Advice.

                                       21
<PAGE>
 
          (e)  Restrictions on Public Sale.
               --------------------------- 

          (1)   Public Sale by Holders of Registrable Securities.  To the extent
                ------------------------------------------------                
     not inconsistent with applicable law, each Stockholder, if requested by the
     managing underwriter or underwriters for any Demand Registration or
     Piggyback Registration, agrees not to effect any public sale or
     distribution of Common Stock (or securities convertible into or
     exchangeable or exercisable for Common Stock), including a sale pursuant to
     Rule 144 (or any similar provision then in force) under the Securities Act,
     during the 15 business days prior to, and during the ninety (90)-day period
     (or such shorter period as may be agreed to by such holders) beginning on,
     the effective date of the applicable Registration Statement (except as part
     of such Registration).

          (2)   Public Sale by the Company and Others.  If requested by the
                -------------------------------------                      
     managing underwriter or underwriters for any underwritten Demand
     Registration or Piggyback Registration, (i) the Company will not effect any
     public sale or distribution of Common Stock (or securities convertible into
     or exchangeable or exercisable for Common Stock) during the fifteen (15)
     business days prior to, and during the ninety (90)-day period beginning on
     the effective date of such Registration and (ii) the Company will cause
     each holder of Common Stock (or securities convertible into or exchangeable
     or exercisable for Common Stock) purchased from the Company at any time
     after the date of this Agreement (other than in a registered public
     offering) to agree not to effect any public sale or distribution of any
     such securities during such period described in clause (i) above (except as
     part of such Registration, if otherwise permitted).

          (3)   Other Registrations.  If the Company has previously filed a
                -------------------                                        
     Registration Statement with respect to Registrable Securities, and if such
     previous Registration has not been withdrawn or abandoned, the Company will
     not file or cause to be effected any other registration of any of its
     Common Stock (or securities convertible into or exchangeable or exercisable
     for Common Stock) under the Securities Act (except on Form S-8 or any
     similar successor form), whether on its own behalf or at the request of any
     holder or holders of Common Stock (or securities convertible into or
     exchangeable or exercisable for Common Stock), until a period of at least
     three (3) months has elapsed from the effective date of such previous
     Registration; provided, that if the holders of fifty percent (50%) or

                                       22
<PAGE>
 
     more of the aggregate number of Registrable Securities included in such
     previous Registration shall agree in writing, such period may be shortened
     to a period specified by such holders.

          (f)   Registration Expenses.
                --------------------- 

          (1)   All expenses incident to the Company's performance of or
     compliance with this Agreement will be borne by the Company, including,
     without limitation, all registration and filing fees, the fees and expenses
     of the counsel and accountants for the Company (including the expenses of
     any "cold comfort" letters and special audits required by or incident to
     the performance of such persons), all other costs and expenses of the
     Company incident to the preparation, printing and filing under the
     Securities Act of the Registration Statement (and all amendments and
     supplements thereto) and furnishing copies thereof and of the Prospectus
     included therein, the costs and expenses incurred by the Company in
     connection with the qualification of the Registrable Securities under the
     state securities or "blue sky" laws of various jurisdictions, the costs and
     expenses associated with filings required to be made with the NASD
     (including, if applicable, the fees and expenses of any "qualified
     independent underwriter" and its counsel as may be required by the rules
     and regulations of the NASD), the costs and expenses of listing the
     Registrable Securities for trading on a securities exchange or authorizing
     them for trading on NASDAQ and all other costs and expenses incurred by the
     Company in connection with any Registration hereunder; provided, that,
                                                            --------       
     except as otherwise provided in subsection (2) below, each Stockholder
     shall bear the costs and expenses of any underwriters' commissions,
     brokerage fees or transfer taxes relating to the Registrable Securities
     sold by such Stockholders and the fees and expenses of any counsel,
     accountants or other representative retained by Stockholder.

          (2)   Notwithstanding the foregoing and except as provided below, in
     connection with each Registration hereunder, the Company will reimburse the
     Stockholders who are holders of Registrable Securities being registered in
     any Registration hereunder for (i) the reasonable fees and disbursements of
     not more than one counsel, which counsel shall be chosen (x) by the holders
     of a majority of the Registrable Securities to be included therein that are
     held by the Demanding Group, in the case of a Demand Registration and 
     (y) otherwise, by the holders of a majority of all

                                       23
<PAGE>
 
     Registrable Securities to be included therein, and (ii) the reasonable out-
     of-pocket expenses (including travel costs) of the holders of Registrable
     Securities in connection with such Registration.

          (g)   Indemnification.
                --------------- 

          (1)   Indemnification by the Company. The Company agrees to indemnify,
     to the full extent permitted by law, each Stockholder, its officers,
     directors, partners and agents and each person who controls such
     Stockholder (within the meaning of the Securities Act and the Securities
     Exchange Act of 1934, as amended (the "Exchange Act")), against all losses,
                                            ------------                        
     claims, damages, liabilities and expenses caused by any untrue or alleged
     untrue statement of a material fact contained in any Registration
     Statement, Prospectus or preliminary Prospectus or any omission or alleged
     omission to state therein a material fact necessary to make the statements
     therein (in the case of a Prospectus or any preliminary Prospectus, in
     light of the circumstances under which they were made) not misleading,
     except insofar as the same are caused by or contained in any information
     with respect to such Stockholder furnished in writing to the Company by
     such Stockholder in its capacity as a selling Stockholder expressly for use
     therein.  The Company will also indemnify underwriters, selling brokers,
     dealer managers and similar securities industry professionals participating
     in the distribution, their officers and directors and each person who
     controls such persons (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; provided, however, if pursuant to an
                                        --------  -------                   
     underwritten public offering of Registrable Securities, the Company and any
     underwriters enter into an underwriting or purchase agreement relating to
     such offering that contains provisions relating to indemnification and
     contribution between the Company and such underwriters, such provisions
     shall be deemed to govern indemnification and contribution as between the
     Company and such underwriters.

          (2)   Indemnification by Holders of Registrable Securities.  In
                ----------------------------------------------------     
     connection with any Registration in which a Stockholder is participating,
     each such Stockholder will furnish to the Company in writing such
     information with respect to such Stockholder as the Company reasonably
     requests for use in connection with any Registration Statement or
     Prospectus and agrees to indemnify, to the full extent permitted by law,
     the

                                       24
<PAGE>
 
     Company, the directors and officers of the Company signing the Registration
     Statement and each person who controls the Company (within the meaning of
     the Securities Act and the Exchange Act) against any losses, claims,
     damages, liabilities and expenses resulting from any untrue statement of a
     material fact or any omission to state a material fact required to be
     stated therein or necessary to make the statements in the Registration
     Statement or Prospectus or preliminary Prospectus (in the case of the
     Prospectus or any preliminary Prospectus, in light of the circumstances
     under which they were made) not misleading, to the extent, but only to the
     extent, that such untrue statement or omission is contained in any
     information with respect to such Stockholder so furnished in writing by
     such Stockholder in its capacity as a selling Stockholder specifically for
     inclusion therein.  In no event shall the liability of any selling holder
     of Registrable Securities hereunder be greater in amount than the dollar
     amount of the net proceeds received by such holder upon the sale of the
     Registrable Securities giving rise to such indemnification obligation.  The
     Company shall be entitled to receive indemnities from underwriters, selling
     brokers, dealer managers and similar securities industry professionals
     participating in the distribution, to the same extent as provided above
     with respect to information with respect to such persons or entities so
     furnished in writing by such persons or entities or their representatives
     specifically for inclusion in any Prospectus or Registration Statement.

          (3)   Conduct of Indemnification Proceedings.  Any person or entity
                --------------------------------------                       
     entitled to indemnification hereunder will (i) give prompt written notice
     to the indemnifying party after the receipt by the indemnified party of a
     written notice of the commencement of any action, suit, proceeding or
     investigation or threat thereof made in writing for which such indemnified
     party will claim indemnification or contribution pursuant to this
     Agreement; provided, however, that the failure of any indemnified party to
                --------  -------                                              
     give notice as provided herein shall not relieve the indemnifying party of
     its obligations under the preceding subparagraphs (1) and (2), except to
     the extent that the indemnifying party is actually prejudiced by such
     failure to give notice and (ii) unless in such indemnified party's
     reasonable judgment a conflict of interest may exist between such
     indemnified and indemnifying parties with respect to such claim, permit
     such indemnifying party to assume the defense of such claim with counsel
     reasonably satisfactory to the indemnified party. Whether or not such
     defense is assumed by the indemnifying party, the indemnifying party will
     not be subject to any liability for any settlement

                                       25
<PAGE>
 
     made without its consent (but such consent will not be unreasonably
     withheld).  No indemnifying party will consent to the entry of any judgment
     or enter into any settlement that does not include as an unconditional term
     thereof the giving by the claimant or plaintiff to such indemnified party
     of a release from all liability in respect of such claim or litigation.  An
     indemnifying party who is not entitled to, or elects not to, assume the
     defense of a claim will not be obligated to pay the fees and expenses of
     more than one counsel in any one jurisdiction 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, in which event the indemnifying party
     shall be obligated to pay the fees and expenses of such additional counsel
     or counsels.

          (4) Contribution.  If for any reason the indemnification provided for
              ------------                                                     
     in the preceding subparagraphs (1) and (2) is unavailable to an indemnified
     party as contemplated by the preceding clauses (1) and (2), then the
     indemnifying party in lieu of indemnification shall contribute to the
     amount paid or payable by the indemnified party as a result of such loss,
     claim, damage, liability or expense in such proportion as is appropriate to
     reflect not only the relative benefits received by the indemnified party
     and the indemnifying party, but also the relative fault of the indemnified
     party and the indemnifying party, as well as any other relevant equitable
     considerations, provided that no Stockholder shall be required to
     contribute in an amount greater than the difference between the net
     proceeds received by such Stockholder with respect to the sale of any
     Shares and all amounts already contributed by such Stockholder with respect
     to such claims, including amounts paid for any legal or other fees or
     expenses incurred by such Stockholder.

          (h) Rule 144.  The Company agrees that at all times after it has filed
              --------                                                          
a registration statement pursuant to the requirements of the Securities Act
relating to any class of equity securities of the Company, it will file in a
timely manner all reports required to be filed by it pursuant to the Securities
Act and the Exchange Act and will take such further action as any holder of
Registrable Securities may reasonably request in order that such holder may
effect sales of Common Stock pursuant to Rule 144.  At any reasonable time and
upon request of any Stockholder, the Company will furnish such Stockholder and
others with such information as may be necessary to enable the Stockholder to
effect sales

                                       26
<PAGE>
 
of Common Stock pursuant to Rule 144 under the Securities Act and will deliver
to such Stockholder a written statement as to whether it has complied with such
requirements. Notwithstanding the foregoing, the Company may deregister any
class of its equity securities under Section 12 of the Exchange Act or suspend
its duty to file reports with respect to any class of its securities pursuant to
Section 15(d) of the Exchange Act if it is then permitted to do so pursuant to
the Exchange Act and the rules and regulations thereunder.

          (i)   Participation in Underwritten Registrations.  No Stockholder may
                -------------------------------------------                     
participate in any underwritten Registration hereunder unless such Stockholder
(i) agrees to sell its Registrable Securities on the basis provided in any
underwriting arrangements approved by the persons entitled hereunder to select
the underwriter pursuant to subsections 4(a)(3) and (4)(b)(4) above, and (ii)
accurately completes in a timely manner and executes all questionnaires, powers
of attorney, underwriting agreements and other documents customarily required
under the terms of such underwriting arrangements.

          (j)   Other Registration Rights.  The Company will not grant to any
                -------------------------                                    
person (including the Stockholders) any demand or piggyback registration rights
with respect to the Common Stock of the Company (or securities convertible into
or exchangeable or exercisable for Common Stock) other than piggyback
registration rights that are not inconsistent with the terms of this Section 4.
To the extent that the Company grants to any person registration rights with
respect to any securities of the Company having provisions more favorable to the
holders thereof than the provisions contained in this Agreement, the Company
will confer comparable rights to the holders of Registrable Securities under
this Agreement.  Except as provided herein, the Company will not grant any
registration rights that would permit any person or entity the right to
piggyback on any Demand Registration.

          (k)   Definition of Registrable Securities.  "Registrable Securities"
                ------------------------------------    ---------------------- 
means the shares of Common Stock now owned or hereafter acquired by any
Stockholder, but with respect to any share, only until such time as such share
(i) has been effectively registered under the Securities Act and disposed of in
accordance with the Registration Statement covering it or (ii) has been sold to
the public pursuant to Rule 144 (or any similar provision then in force) under
the Securities Act and the Legend referred to in Section 6(a) has been removed
from the certificate representing such share (at which time such share shall
cease to be a Registrable Security).

          (l)   Amendments and Waivers.  The provisions of this Section 4,
                ----------------------                                    
including the provisions of this sentence, may not be amended, modified or
supplemented,

                                       27
<PAGE>
 
and waivers of or consents to departures from the provisions hereof may not be
given unless approved by the Company in writing and the Company has obtained the
written consent of Stockholders holding at least eighty-five percent (85%) of
the then outstanding Registrable Securities (including for such purposes all
securities convertible into or exchangeable for Registrable Securities, other
than the Warrants).  Notwithstanding the foregoing, any amendment, waiver or
consent that materially and adversely affects any of the By-Word Stockholders as
a group, the Erin Mills Stockholders as a group, the Carlyle Stockholders as a
group, the Clipper Stockholders as a group or SBW differently from the other
Stockholders, shall require the prior written approval of the holders of at
least a Majority in Interest of Stockholders who are then members of the group
or the entity so affected.

          Section 5.    Governance.
                        ---------- 

          (a) Within fifteen days after the execution hereof, the total number
of members of the Board of Directors will be reduced to six, which number shall
be adjusted from time to time in order to give effect to the provisions of
subsection (b) below.  The Company and the Stockholders hereby agree to take, at
any time and from time to time, all action necessary (including, without
limitation, voting the shares of Company Common Stock owned or controlled by
such Stockholder, calling special meetings of stockholders, executing and
delivering written consents and requiring designees to resign) to establish the
number of total number of directors as provided herein.

          (b) At all times from and after fifteen days after the execution
hereof (except for the addition of a second Independent Director, which shall
occur no later than the date of the next annual meeting of the stockholders of
the Company), the Board of Directors of the Company (the "Board") shall be
                                                          -----           
composed of Directors to be designated in the manner set forth below.  The
Company and each Stockholder hereby agree to take, at any time and from time to
time, all action necessary (including, without limitation, voting the shares of
the Company Common Stock owned or controlled by such Stockholder, calling
special meetings of stockholders and executing, delivering written consents and
requiring designees to resign) to elect Directors as provided herein.  Prior to
the receipt of Regulatory Relief, the Board shall be composed of seven (7)
members, of which two (2) Directors shall be persons designated by a Majority in
Interest of the Erin Mills Stockholders, two (2) Directors shall be persons
designated by a Majority in Interest of the By-Word Stockholders (one of which
shall be the chief executive officer of the Company), one (1) Director shall be
a person designated by a Majority in Interest of the Carlyle Stockholders and
two (2) additional Directors (or, if determined by the Nominating Committee as
hereinafter provided, three (3) additional Directors) shall be persons who are

                                       28
<PAGE>
 
not employed by the Company or affiliated with any party to this Agreement
("Independent Directors").  SBW shall be entitled to designate one non-director
delegate who shall be entitled to receive notice of, in accordance with the
provisions of Section 11.6 of the Bylaws with respect to Class B Directors, and
to attend all meetings of the Board and to receive all materials received by
Directors, but who shall not be a member of the Board of Directors, shall have
no fiduciary duties to the Company, to the Board or stockholders of the Company
and shall not be entitled to vote at meetings of the Board.  Upon the conversion
of the Series D Preferred Stock into Class B Common Stock, the number of
Directors shall be increased by one who shall be a person designated by SBW and
the right to a non-director delegate shall terminate.  If SBW and its Affiliates
Beneficially Own 20% or more of the Common Stock (including Common Stock
issuable upon conversion of Series D Preferred Stock or Class B Common Stock or
other convertible securities or upon the exercise of any outstanding options,
warrants, rights or obligations, other than shares issuable upon exercise of the
Warrants and Excluded Options) on a Fully Diluted Basis, the number of Directors
shall further be increased by one and the additional Director shall also be a
designee of SBW.  For so long as SBW or its Affiliates hold Class B Common
Stock, one or both of SBW's designees will be elected by SBW as the holder of
the Class B Common Stock and will be Class B Directors, with the rights set
forth in the terms of such Class B Common Stock and the Bylaws, and which
directors will have the corporate authority to sign a stockholder consent of SBW
on behalf of each of the SBW Stockholders.

          All Independent Directors shall be nominated by a committee consisting
of one Director designated by the Erin Mills Stockholders, one Director
designated by the By-Word Stockholders, one Director designated by the Carlyle
Stockholders and, following receipt of Regulatory Relief, one Director
designated by SBW (the "Nominating Committee").  The Nominating Committee also
shall determine whether to increase the number of Independent Directors to three
(3).

          Notwithstanding the foregoing, no Stockholder or group of Stockholders
shall be entitled to designate any Director or have such designee serve on the
Nominating Committee if the percentage of Common Stock (including Common Stock
issuable upon conversion of outstanding securities or upon the exercise of any
outstanding options, warrants, rights or obligations other than the Warrants and
Excluded Options) Beneficially Owned by such Stockholder or group of
Stockholders falls below 5% (or, with respect to the Erin Mills Stockholders and
By-Word Stockholders, 20% for the right to designate two Directors and 5% for
the right to designate one Director) on a Fully Diluted Basis.  If By-Word has
only one designee, it shall be the chief executive officer of the Company if the
chief executive officer is a By-Word Stockholder.  Upon the failure of any
Stockholder or

                                       29
<PAGE>
 
group of Stockholders to maintain the required percentage, the Stockholder or
group of Stockholders shall require its designee to resign and the size of the
Board may, in the determination of the Nominating Committee, either be reduced
to eliminate such the resulting vacancy on the Board or remain the same (in
which case, the resulting vacancy on the Board will be filled by a Director
nominated by the Nominating Committee), provided that the Stockholders agree
that if the chief executive officer is not a By-Word designee, in accordance
with the provisions hereof, the chief executive officer shall be nominated by
the Nominating Committee.

          (c) Pursuant to Article VII of the Incentive Stock Option Plan, the
Board shall appoint a three-person Compensation Committee to administer the
Incentive Stock Option Plan.  Following receipt of Regulatory Relief, a Director
designated by SBW shall serve on the Compensation Committee.  The Compensation
Committee shall be comprised of only non-management Directors serving on the
Board.  Each Stockholder hereby agrees to take, at any time and from time to
time, all action necessary (including, without limitation, voting the shares of
the Common Stock owned or controlled by such Stockholder, calling special
meetings of stockholders and executing and delivering written consents) to cause
the Board to appoint to the Compensation Committee the number of persons meeting
the requirements of this subsection.

          (d) The Stockholders agree that no Director may be removed except at
the request of the holders of a majority of the shares of Common Stock entitled
to appoint such Director in accordance with Section 5(b), and each Stockholder
hereby agrees to take all action necessary (including, without limitation,
voting the shares of Common Stock owned or controlled by such Stockholder,
calling special meetings of stockholders and executing and delivering written
consents) for the purpose of accomplishing the purposes of this Agreement.  If a
vacancy on the Board occurs by reason of the death, removal, resignation,
retirement or election not to serve of a designee, the remaining Directors and
the Company shall cause the vacancy thereby created to be filled by a new
designee as soon as possible (the "Replacement Director"), who is designated in
                                   --------------------                        
the same manner and by the same persons specified in Section 5(b) as the
Director being replaced had been, and the Company and each Stockholder hereby
agrees to take, at any time and from time to time, all actions necessary to
accomplish the same; provided, however, that if any group fails to designate a
                     --------  -------                                        
representative in accordance with Section 5(b) above for a period of thirty (30)
consecutive days, then such vacancy shall be filled by the Nominating Committee
until such time as the Replacement Director is designated in accordance with
Section 5(b), at which time the term of the Director not elected in accordance
with Section 5(b) shall expire.

                                       30
<PAGE>
 
          (e) In addition to any compensation to which the members of the Board
may be entitled, the Company shall reimburse each Director for the reasonable
out-of-pocket expenses incurred by such Director (including, without limitation,
reasonable fees and expenses of counsel, accountants, or representatives, if
any) involved with such Director's services as a member of the Company.  In
addition, the Company shall obtain and maintain at all times during which this
Agreement remains in effect, at the cost and expense of the Company, director
liability insurance policies covering each member of the Board.  Such director
liability insurance policies shall be provided by a reputable nationally
recognized insurance carrier and shall provide coverage in such amounts and on
such terms as may be reasonably acceptable to each member of the Board.  Should
SBW so request, the Company will enter into contractual indemnification
arrangements with the Director reasonably satisfactory to SBW.

          (f) In addition to any vote or consent of the Board of Directors or
its stockholders required by law or the Certificate of Incorporation, including
the terms of Series D Preferred Stock and the Class B Common Stock, the
affirmative vote of a majority of the entire Board of Directors (not merely a
quorum) shall be necessary for authorizing, effecting or validating the
following actions:

          (i) the approval of any annual budget or business plan for the Company
     or any Subsidiary of the Company or the deviation by the Company or any
     such Subsidiary from any annual budget for the Company or such Subsidiary
     approved by the Board of Directors by more than five percent (5%);

          (ii) any capital expenditure or expenditures by the Company or any
     Subsidiary of the Company which, individually or in the aggregate, exceeds
     $1,000,000;

          (iii)  the hiring or termination by the Company or any Subsidiary of
     the Company of any officer or senior management employee of the Company or
     such Subsidiary;

          (iv) directly or indirectly redeem, purchase or make any payments with
     respect to any stock appreciation rights, phantom stock plans or similar
     rights or plans;

          (v) (A) sell, lease, transfer or otherwise convey, or permit any
     Subsidiary to sell, lease, transfer or otherwise convey, any assets

                                       31
<PAGE>
 
     representing five percent (5%) or more of the consolidated assets of the
     Company and its Subsidiaries, (B) consolidate or merge with, or permit any
     Subsidiary to consolidate or merge with, any Person, (C) reclassify or
     otherwise change, or permit any Subsidiary to reclassify or otherwise
     change, any capital stock of the Company or any Subsidiary or (D) dissolve,
     liquidate or wind-up the Company or permit any Subsidiary to dissolve,
     liquidate or wind up such Subsidiary.

          (vi) except as expressly contemplated by the Purchase Agreement or the
     any of the Transaction Documents, authorize, issue or enter into any
     agreement providing for the issuance, or permit any Subsidiary to
     authorize, issue or enter into any agreement providing for the issuance
     (contingent or otherwise) in excess of an aggregate of $5,000,000 (A) any
     notes or debt securities containing equity features (including, without
     limitation, any note or debt securities convertible into or exchangeable
     for capital stock or other equity securities, issued in connection with the
     issuance of capital stock or other equity securities, or containing profit
     participation features) or (B) any capital stock or other equity
     securities, or any securities convertible into or exchangeable for any
     capital stock or other equity securities, other than issuances pursuant to
     the Incentive Stock Option Plan;

          (vii)  acquire, or permit any Subsidiary to acquire, in one
     transaction or a series of related transactions, any capital stock, other
     equity interests or assets of any Person for aggregate consideration in
     excess of $5,000,000;

          (viii)  enter into, or permit any Subsidiary to enter into, any
     agreement, contract, lease or commitment on the part of the Company or such
     Subsidiary involving the payment or provision of consideration by or to the
     Company or such Subsidiary, the fair market value of which exceeds
     $1,000,000;

          (ix)  make any capital expenditure, or permit any Subsidiary to make
     any capital expenditure, in excess of $1,000,000;

          (x)  except as expressly contemplated by the Purchase Agreement, amend
     the Certificate of Incorporation, or the Company's bylaws or file any
     resolution of the board of directors with the Secretary of State of the
     State

                                       32
<PAGE>
 
     of Delaware containing any provisions which would adversely affect or
     otherwise impair the rights of the holders of the Common Stock;

          (xi) enter into, or permit any Subsidiary to enter into, any
     agreement, transaction, commitment or arrangement with any of its or any
     Subsidiary's officers, directors, employees, stockholders or Affiliates or
     with any individual related by blood, marriage or adoption to any such
     individual or with any entity in which such Person or individual own, in
     the aggregate, a more than 10% beneficial interest, except for 
     (A) customary employment arrangements and benefit programs on arms' length
     terms and (B) agreements, transactions, commitments or arrangements on
     arms' length terms and approved by a majority of the Company's
     disinterested directors; or

          (xii)  enter into, or permit any Subsidiary to enter into, any
     agreement to do or effect any of the foregoing.

     (g) Following the receipt of Regulatory Relief, if SBW does not hold any
Series D Preferred Stock or Class B Common Stock but does own at least 1.6
million shares of Common Stock (including Common Stock issuable upon conversion
of outstanding securities or upon the exercise of any outstanding options,
warrants, rights or obligations, other than the Warrants and Excluded Options)
on a Fully Diluted Basis, the approval of SBW shall be required for the
following actions:

          (i) the approval of any annual budget or business plan for the Company
     or any Subsidiary of the Company or the deviation by the Company or any
     such Subsidiary from any annual budget for the Company or such Subsidiary
     approved by the Board of Directors by more than five percent (5%);

          (ii) issuance by the Company of any equity securities, including
     securities convertible into equity securities (other than (A) the grant of
     employee stock options (subject to the proviso set forth in (D) below), 
     (B) the issuance of equity securities in accordance with the terms of the
     Purchase Agreement or any of the other Transaction Documents), (C) the
     issuance of equity securities upon the exercise or conversion of securities
     or employee stock options that are outstanding as of the date hereof or 
     (D) the issuance of equity securities after giving effect to the
     consummation of the transactions contemplated hereby or employee stock
     options granted

                                       33
<PAGE>
 
     hereafter, provided, however, that there shall not be outstanding at any
                --------  -------                                            
     time employee stock options for more than 1.5 million shares of Common
     Stock plus the options granted to William C. Kennedy, Jr. and William C.
     Saunders that are outstanding at September 27, 1996) or incurrence of any
     indebtedness for borrowed money or evidenced by bonds, notes or debentures,
     provided that the Company can incur up to $5 million in indebtedness in any
     year without the consent of SBW;

          (iii)  the hiring or termination by the Company of its chief executive
     officer, chief operating officer or chief financial officer;

          (iv) the Company's entering into any lines of business which is not
     its Existing Line of Business (as hereinafter defined) or any joint
     ventures, partnerships or similar arrangements;

          (v) the Company's exiting its Existing Line of Business (as
     hereinafter defined) or disposing of assets (other than telecommunications
     equipment and other assets sold in the ordinary course of business) in any
     year with a value in excess of $500,000 or which are otherwise material to
     the Company's operations;

          (vi) the adoption, implementation or acceptance (including the failure
     to opt out) of any Anti-Takeover Provision not in effect as of the date
     hereof that would be applicable to, and, in the reasonable determination of
     SBW, adversely affect, SBW and its Affiliates; or

          (vii)  the taking of any corporate action that would reduce the number
     of Shares held by SBW and its Affiliates to fewer than 1.6 million shares
     of Common Stock such that SBW no longer has the right to approve any of the
     actions specified in this subsection (g).

          As used in this subsection (g), the terms set forth below shall have
the following respective meanings;

          "Anti-takeover Provision" means (i) any provision of the certificate
of incorporation or bylaws of the Company or any contract, agreement or plan to
which the Company is a party or by which it is bound or any statutory provision
enacted after the date hereof which is applicable to the Company which the
Company may opt out of if the effect of such provision would be to materially
delay, hinder or prevent a change in control of the

                                       34
<PAGE>
 
Company or (ii) a stockholder rights plan or "poison pill," including the
provisions of any preferred stock or common stock purchase rights issued
pursuant thereto; provided, however, that such term shall not include any
customary change of control provisions contained in employment agreements
between the Company and any of its directors, officers or other employees or in
any plans or agreements relating to stock options or other awards of equity
securities made by the Company to any such persons.

          "Existing Line of Business" means a non-facilities based, enhanced
service provider that offers fleet management and/or status or information about
vehicles and/or location capabilities through mobile communications service.

          (h) The Board shall hold, during the term of this Agreement, regularly
scheduled, in-person meetings no less frequently than six times per year.

          (i) At all times during which this Agreement remains in effect, each
Stockholder hereby agrees to take all action necessary (including, without
limitation, voting the shares of the Company's Common Stock owned or controlled
by such Stockholder, calling special meetings of stockholders and executing and
delivering written consents) to ensure that the By-Laws of the Company provide
that the information listed on Schedule A hereto shall be provided to each
member of the Board of Directors, at the time and in the manner required by the
provisions of Schedule A.

          (j) The Company and each Stockholder agrees not to, and to cause its
designees on the Board not to, without the prior approval of SBW, alter, amend,
repeal or replace the Bylaws set forth on Exhibit B hereto or to enact any
Bylaws inconsistent therewith.

          (k) For the purpose of this Section 5, Chase Manhattan Investment
Holdings, Inc., Archery Partners and their respective assigns shall not be
considered Carlyle Stockholders.

           Section 6.    Miscellaneous.
                         ------------- 

          (a) Legend.  The certificates representing the capital stock of the
              ------                                                         
Company held by each of the Stockholders shall bear the following legend
(provided that with respect to SBW and any certificates issued after the date
hereof such legend shall refer to this Agreement):

                                       35
<PAGE>
 
          "THE SECURITIES EVIDENCED BY THIS CERTIFICATE HAVE NOT BEEN REGISTERED
UNDER THE SECURITIES ACT OF 1933 OR THE SECURITIES LAWS OF ANY STATE AND MAY NOT
BE SOLD OR TRANSFERRED UNLESS THERE IS AN EFFECTIVE REGISTRATION STATEMENT
COVERING SUCH SECURITIES OR SUCH SALE OR TRANSFER IS EXEMPT FROM THE
REGISTRATION AND PROSPECTUS DELIVERY REQUIREMENTS OF SUCH ACT AND ANY SIMILAR
REQUIREMENTS OF ANY APPLICABLE STATE SECURITIES LAW.  THE SECURITIES REPRESENTED
BY THIS CERTIFICATE ARE SUBJECT TO CERTAIN RESTRICTIONS SET FORTH IN A
STOCKHOLDERS AGREEMENT DATED AS OF FEBRUARY 4, 1994, A COPY OF WHICH IS
AVAILABLE UPON REQUEST FROM THE SECRETARY OF THE COMPANY."

          If any capital stock of the Company becomes eligible for sale pursuant
to Rule 144(k) promulgated under the Securities Act, the Company shall, subject
to applicable law and upon the request of any holder of such capital stock,
remove the legend set forth in this Section 6(a) from the certificates
evidencing the shares of such capital stock held by such holder.  In addition,
(i) in connection with any Transfer of shares of any capital stock of the
Company pursuant to any public offering registered under the Securities Act or
pursuant to Rule 144 (or any similar rule or rules then in effect promulgated
under the Securities Act) if such rule is available or (ii) if the holder of any
shares of capital stock of the Company delivers to the Company an opinion of
counsel reasonably acceptable to the Company that no subsequent Transfer of such
shares shall require registration under the Securities Act, the Company shall
promptly upon such Transfer deliver new certificates for such shares which do
not bear the legend set forth in this Section 6(a).

          (b) Successors, Assigns and Transferees.  This Agreement shall be
              -----------------------------------                          
binding upon and inure to the benefit of the parties hereto, their respective
legal representatives, heirs, legatees, successors and permitted assigns.  The
only permitted assigns (each, a "Permitted Assign") are as follows:  (i) each of
the Clipper Stockholders shall be entitled to assign any of its rights under
this Agreement to any other Clipper Stockholder; (ii) each of the Carlyle
Stockholders shall be entitled to assign any of its rights under this Agreement
to any other Carlyle Stockholder or any Related Party of a Carlyle Stockholder
(other than an Excluded Related Party); (iii) each of the By-Word Stockholders
shall be entitled to assign any of its rights under this Agreement to any other
By-Word Stockholder; (iv) each of the Erin Mills Stockholders shall be entitled
to assign any of its rights under this Agreement to any other Erin Mills
Stockholder or any Related Party of an Erin Mills Stockholder (other than an
Excluded Related Party) and (v) SBW shall be entitled to assign any of its
rights under this Agreement to any of its Affiliates.  No party hereto shall be
entitled to assign any of its rights under this Agreement to any Person which

                                       36
<PAGE>
 
is otherwise a Permitted Assign hereunder unless, concurrently with such
assignment, such party is Transferring all or a portion of the Shares owned by
it to such Person in compliance with the terms and provisions set forth herein
and such Person executes a supplemental agreement hereto in form and substance
reasonably satisfactory to the Company pursuant to which such Person agrees to
become a party to, and be bound by, this Agreement.

          (c) Specific Performance, Etc.  The Company and each Stockholder, in
              -------------------------                                       
addition to being entitled to exercise all rights provided herein, in the
Company's Certificate of Incorporation or granted by law, including recovery of
damages, will be entitled to specific performance of its rights under this
Agreement.  The Company and each Stockholder agrees that monetary damages would
not be adequate compensation for any loss incurred by reason of a breach by it
of the provisions of this Agreement and hereby agrees to waive the defense in
any action for specific performance that a remedy at law would be adequate.

          (d) Governing Law.  This Agreement shall be governed by and construed
              -------------                                                    
in accordance with the internal law of the State of Delaware without giving
effect to the conflict of laws provisions thereof.

          (e) Interpretation.  The headings of the sections contained in this
              --------------                                                 
Agreement are solely for the purpose of reference, are not part of the agreement
of the parties and shall not affect the meaning or interpretation of this
Agreement.

          (f) Notices.  Any notice or other communication required or permitted
              -------                                                          
hereunder shall be in writing and shall be delivered personally, sent by
facsimile transmission or sent by certified, registered or express mail, postage
prepaid.  SBW agrees to give the Company written notice when Regulatory Relief
has been obtained.  Any such notice shall be deemed given when so delivered
personally, sent by facsimile transmission or, if mailed, three (3) business
days after the date of deposit in the United States mail, by certified mail
return receipt requested, as follows:

          (i)  If to the Company to:

               HighwayMaster Communications, Inc.
               16479 Dallas Parkway, Suite 710
               Dallas, Texas 75248
               Attention: William Kennedy
               Telecopier: (972) 930-7263

                                       37
<PAGE>
 
               with a copy (which shall not constitute notice) to:

               Baker & Botts, L.L.P.
               2001 Ross Avenue
               Dallas, Texas  75201
               Attention:  Geoffrey L. Newton
               Telecopier: (214) 953-6503

         (ii)  If to any of the Carlyle Entitles, to

               c/o The Carlyle Group, L.P.
               1001 Pennsylvania Avenue, N.W.
               Suite 220 South
               Washington, D.C. 20004-2505
               Attention: Mark D. Ein
               Telecopier: (202) 347-1818

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

               Latham & Watkins
               1001 Pennsylvania Avenue, N.W.
               Suite 1300
               Washington, D.C. 20004-2505
               Attention: Bruce E. Rosenblum, Esq.
               Telecopier:  (202) 637-2201

                                       38
<PAGE>
 
        (iii)  If to any of the Clipper Entities, to

               The Clipper Group, L.P.
               12 East 49th Street
               New York, N.Y. 10017
               Attention: Daniel V. Cahillane
               Telecopier: (212) 318-1360

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

               Weil, Gotshal & Manges, LLP
               767 Fifth Avenue
               New York, N.Y. 10153
               Attention: Howard Chatzinoff
               Telecopier: (212) 310-8007

         (iv)  If to any of the Erin Mills Companies, to

               Erin Mills International
               Trident House, Suite 204(a)
               Broad Street
               Bridgetown, Barbados
               West Indies
               Attention: Stephen Greaves
               Telecopier:  (809) 436-2120

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

               7501 Keele Street, Suite 500
               Concord, Ontario L4K 1Y2
                     Canada
               Attention: Gerry C. Quinn
               Telecopier: (416) 736-8373

                                       39
<PAGE>
 
          (v)  If to any of the By-Word Stockholders, to:

               HighwayMaster Communications, Inc.
               16479 Dallas Parkway
               Suite 710
               Dallas, Texas 75248
               Attention: William Kennedy
               Telecopier: (972) 930-7263

         (vi)  If to Chase Manhattan Investment Holdings, Inc. or Archery
Partners:

               The Chase Manhattan Bank
               One Chase Plaza
               New York, NY 10081
               Attention: William K. Luby
               Telecopier: (212) 552-2958

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

               Kirkland & Ellis
               200 East Randolph Drive
               Chicago, IL 60601
               Attention: Emile Karafiol
               Telecopier: (312) 861-2200

                                       40
<PAGE>
 
          (vii)   If to Southwestern Bell Wireless Holdings, Inc.

                  Southwestern Bell Wireless Holdings, Inc.           
                  17330 Preston Road                                  
                  Suite 100A                                          
                  Dallas, Texas 75252                                 
                  Attention: President                                
                  Telecopier:  (972) 733-2012                         
                                                                      
                  and to:                                             
                                                                      
                  SBC Communications, Inc.                            
                  175 E. Houston                                      
                  San Antonio, Texas 78205                            
                  Attention: General Attorney, Mergers & Acquisitions 
                  Telecopier: (210) 351-3488                          
                                                                      
                  with a copy (which shall not constitute notice) to: 
                                                                      
                  Sullivan & Cromwell                                 
                  125 Broad Street                                    
                  New York, New York  10004                           
                  Attention: Janet T. Geldzahler                      
                  Telecopier: (212) 558-3588                           


Any party may change its address for notice by written notice to the other
parties in accordance with this provision.

          (g)     Termination.   This Agreement will terminate and the Original
                  -----------                                                  
Agreement, as in effect on the date prior to the date hereof, will be deemed to
be in effect if the Purchase Agreement is terminated pursuant to Section 2(c)
thereof.  Sections 3(b) and (c) hereof shall terminate at that time that SBW and
its Affiliates cease to own at least 1.6 million shares of Common Stock
(including Common Stock issuable upon conversion of outstanding securities or
upon the exercise of any outstanding options, warrants, rights or obligations,
other than the Warrants and Excluded Options).

                                       41
<PAGE>
 
          (h) Inspection and Compliance with Law.  Copies of this Agreement will
              ----------------------------------                                
be available for inspection or copying by any Stockholder at the offices of the
Company through the Secretary of the Company.

          (i) Amendments and Waivers.  The provisions of this Agreement,
              ----------------------                                    
including the provisions of this paragraph (h), may not be amended, modified or
supplemented, and waivers of or consents to departures from the provisions
hereof may not be given, except by a written instrument executed by (i) the
Company, (ii) a Majority in Interest of the By-Word Stockholders, (iii) a
Majority in Interest of the Carlyle Stockholders and the Clipper Stockholders
acting as a group, (iv) a Majority in Interest of the Erin Mills Stockholders
and (v) SBW; provided, however, that amendments of or modification to Section 4
             --------  -------                                                 
will be subject to the requirements of Section 4(k).  No action taken pursuant
to this Agreement, including, without limitation, any investigation by or on
behalf of any party, shall be deemed to constitute a waiver by the party taking
such action. The waiver by any party hereto of a breach of any provision of this
Agreement shall not operate or be construed as waiver of any preceding or
succeeding breach and no failure by any party to exercise any right or privilege
hereunder shall be deemed a waiver of such party's rights or privileges
hereunder or shall be deemed a waiver of such party's rights to exercise the
same at any subsequent time or times hereunder.

          (j) Transfer Void.  Any Transfer of any security of the Company in
              -------------                                                 
violation of this Agreement shall be null and void and the Company covenants and
agrees that it will not register or otherwise recognize a Transfer (whether for
the purposes of shareholder voting or in connection with the distribution of
dividends or other corporate assets) of any securities which it has reason to
believe was effected in violation of this Agreement.

          (k) Counterparts.  This Agreement may be executed in one or more
              ------------                                                
counterparts, by the original parties hereto and any successor in interest, each
of which shall be deemed to be an original and all of which together shall be
deemed to constitute one and the same agreement.

          (l) Attorneys' Fees.  In any action or proceeding brought to enforce
              ---------------                                                 
any provision of this Agreement, or where any provision hereof is validly
asserted as a defense, the successful party shall be entitled to recover
reasonable attorneys' fees in addition to any other available remedy.

          (m) Severability.  In the event that any one or more of the provisions
              ------------                                                      
contained herein, or the application thereof in any circumstances, is held
invalid, illegal or

                                       42
<PAGE>
 
unenforceable in any respect for any reason, the validity, legality and
enforceability of any such provision in every other respect and of the remaining
provisions contained herein shall not be in any way impaired thereby.

                                       43
<PAGE>
 
       IN WITNESS WHEREOF, the parties have executed this Agreement as of the
date first above written.

                 HIGHWAYMASTER COMMUNICATIONS, INC.,



                 By: /s/ William C. Saunders
                    -------------------------------------------------
                         Name: William C. Saunders
                               --------------------------------------
                         Title: President
                                -------------------------------------


                SOUTHWESTERN BELL WIRELESS HOLDINGS,
                           INC.


                By: /s/ Stan Sigman
                   --------------------------------------------------
                         Name: Stan Sigman
                               --------------------------------------
                         Title: President & Chief Executive Officer
                                -------------------------------------


                CARLYLE-HIGHWAYMASTER INVESTORS, L.P.
                By:      TC Group, L.L.C., its General Partner


                         By: /s/ Mark D. Ein
                             ----------------------------------------
                         Name: Mark D. Ein
                               --------------------------------------
                         Title: Vice-President of Managing Partner of
                                -------------------------------------      
                                TC Group
                                -------------------------------------


                CARLYLE-HIGHWAYMASTER INVESTORS II, L.P.
                By: TC Group, L.L.C., its General Partner


                    By: /s/ Mark D. Ein
                       ----------------------------------------------
                        Name: Mark D. Ein
                              ---------------------------------------
                        Title: Vice-President of Managing Partner of
                               --------------------------------------           
                               TC Group
                               --------------------------------------

                                       44
<PAGE>
 
                H.M. RANA INVESTMENTS LIMITED


                By: /s/ Fahad A. Almubarak
                   ---------------------------------------------

                    By:-----------------------------------------
                       Name: Fahad A. Almubarak
                             -----------------------------------
                       Title: President
                              ----------------------------------
              
                TC GROUP, L.L.C.


                By: /s/ Mark D. Ein
                   ---------------------------------------------
                    Name: Mark D. Ein
                         ---------------------------------------
                    Title: Vice-President of Managing Partner of
                           -------------------------------------               
                           TC Group
                           --------

                  /s/ Mark D. Ein
                 -----------------------------------------------
                 Mark D. Ein


                CHASE MANHATTAN INVESTMENT HOLDINGS, INC.


                By: /s/ Jeffrey C. Walker
                   ---------------------------------------------
                    Name: Jeffrey C. Walker
                         ---------------------------------------
                    Title: Chief Executive Officer
                          --------------------------------------


                ARCHERY PARTNERS

                By: /s/ Jeffrey C. Walker, Managing Partner
                   ---------------------------------------------
                    its General Partner

                    By:
                       -----------------------------------------
                          Name: Jeffrey C. Walker
                                --------------------------------
                          Title: Managing Partner
                                 -------------------------------

                                       45
<PAGE>
 
                CLIPPER CAPITAL ASSOCIATES, L.P.
                By: Clipper Capital Associates, Inc.
                    its General Partner


                    By: /s/ Daniel V. Cahillane
                       ----------------------------------------------
                    Name: Daniel V. Cahillane
                          -------------------------------------------
                    Title: Treasurer & Secretary
                           ------------------------------------------


                CLIPPER/MERCHANT PARTNERS, L.P.
                By: Clipper Capital Associates, L.P.,
                    its General Partner
                    By: Clipper Capital Associates, Inc.
                        its General Partner


                    By: /s/ Daniel V. Cahillane
                        ---------------------------------------------
                    Name: Daniel V. Cahillane
                          -------------------------------------------
                    Title: Treasurer & Secretary
                           ------------------------------------------


                CLIPPER/MERBAN, L.P.
                By: Clipper Capital Associates, L.P.
                    its General Partner
                    By: Clipper Capital Associates, Inc.
                        its General Partner


                        By: /s/ Daniel V. Cahillane
                            -----------------------------------------
                        Name: Daniel V. Cahillane
                              ---------------------------------------
                        Title: Treasurer & Secretary
                               --------------------------------------

                ERIN MILLS INTERNATIONAL INVESTMENT
                    CORPORATION

                By: /s/ Stephen L. Greaves
                    -------------------------------------------------
                Name: Stephen L. Greaves
                      -----------------------------------------------
                Title: General Manager
                       ----------------------------------------------

                                       46
<PAGE>
 
                THE ERIN MILLS DEVELOPMENT CORPORATION


                By: /s/ G. C. Quinn
                   -----------------------------------------------------
                    Name: G. C. Quinn
                         -----------------------------------------------
                    Title: Executive Vice-President
                          ----------------------------------------------


                THE ERIN MILLS INVESTMENT CORPORATION


                By: /s/ G. C. Quinn
                   -----------------------------------------------------
                    Name: G. C. Quinn
                         -----------------------------------------------
                    Title: President
                          ----------------------------------------------


                  /s/ William C. Kennedy, Jr.
                 -------------------------------------------------------
                    William C. Kennedy, Jr.


                 -------------------------------------------------------
                    Donald M. Kennedy


                  /s/ William C. Saunders
                 -------------------------------------------------------
                    William C. Saunders


                  /s/ Robert T. Hayes by Douglas Dunlap attorney-in-fact
                 -------------------------------------------------------
                    Robert T. Hayes


                  /s/ Robert S. Folsom by Haddon O. Winckler attorney-in-fact
                 ------------------------------------------------------------
                    Robert S. Folsom

                                       47
<PAGE>
 
       The undersigned are executing this Agreement solely for the purpose of
evidencing their approval of the amendment and restatement of the Original
Agreement (as amended from time to time) in its entirety as set forth herein, it
being understood that the undersigned shall not be deemed Stockholders for
purposes of this Agreement and shall not have any rights or obligations
hereunder.


                  /s/ Margaret D. Folsom
                 ----------------------------------------------------
                      Margaret D. Folsom


                  /s/ R. Stephen Folsom
                 ----------------------------------------------------
                      R. Stephen Folsom


                 ----------------------------------------------------
                      Joann Hayes


                  /s/ Cynthia Ann Hayes
                 ----------------------------------------------------
                      Cynthia Ann Hayes


                  /s/ Alicia Ellen Hayes
                 ----------------------------------------------------
                      Alicia Ellen Hayes

                                       48
<PAGE>
 
                                                                      Appendix A

                                Original Parties

Carlyle-HighwayMaster Investors, L.P.
Carlyle-HighwayMaster Investors II, L.P.
Chase Manhattan Investment Holdings, Inc.
Clipper/Merban, L.P.
Clipper/Merchant Partners, L.P.
Clipper Capital Associates, L.P.
Erin Mills International Investment Corporation
FU Enterprises Ltd.
By-Word Technologies, Inc.
Robert S. Folsom
Robert T. Hayes

                                      A-1
<PAGE>
 
                                                                      Appendix B

                             Amendments and Addenda

                                        
  7.   Addendum No. 1 to Subscription Agreement and Stockholders Agreement by
and among HM Holding Corporation, Carlyle-HighwayMaster Investors, L.P.,
Carlyle-HighwayMaster Investors II, L.P., H.M. Rana Investments Limited, TC
Group, L.L.C., Chase Manhattan Investment Holdings, Inc., Clipper/Merban, L.P.,
Clipper Merchant Partners, L.P., Clipper Capital Associates, L.P., Erin Mills
International Investment Corporation, FU Enterprises Ltd., By-Word Technologies,
Inc., Robert S. Folsom and Robert T. Hayes.

  8.   Consent of Security Holders of HM Holding Corporation and Second
Amendment to Stockholders' Agreement, dated November, 1994, among HM Holding
Corporation, By-Word Technologies, Inc., the former shareholders of By-Word
Technologies, Inc. listed on Exhibit A, Clipper/Merban, L.P., Clipper Merchant
                             ---------                                        
Partners, L.P., Clipper Capital Associates, L.P., Carlyle-HighwayMaster
Investors, L.P., Carlyle-HighwayMaster Investors II, L.P., TC Group, L.L.C.,
H.M. Rana Investments Limited, Chase Manhattan Investment Holdings, Inc., Erin
Mills International Investment Corporation, Robert S. Folsom and Robert T.
Hayes.

  9.   Joinder Agreement to Stockholders Agreement executed as of January 3,
1995 by Mark D. Ein.

  10.  Third Amendment to Stockholders Agreement, dated as of April 28, 1995,
among HighwayMaster Communications, Inc., Archery Partners, Chase Manhattan
Investment Holdings, Inc., Carlyle-HighwayMaster Investors, L.P., Carlyle-
HighwayMaster Investors II, L.P., H.M. Rana Investments Limited, TC Group,
L.L.C., Clipper/Merban, L.P., Clipper Merchant Partners, L.P., Clipper Capital
Associates, L.P., Erin Mills International Investment Corporation, Robert S.
Folsom, Margaret D. Folsom, R. Stephen Folsom, Robert T. Hayes, Cynthia Ann
Hayes, Alicia Ellen Hayes, Joann Hayes, William C. Saunders, William C. Kennedy,
Jr. and Donald M. Kennedy.

          11.  Note Exchange and Amendments Agreement, dated as of May 26, 1995,
among HighwayMaster Communications, Inc., Archery Partners, Chase Manhattan
Investment Holdings, Inc., Carlyle-HighwayMaster Investors, L.P., Carlyle-
HighwayMaster Investors II, L.P., H.M. Rana Investments Limited, TC Group,
L.L.C., Clipper/Merban, L.P., Clipper Merchant Partners, L.P., Clipper Capital
Associates, L.P.,

                                      B-1
<PAGE>
 
Erin Mills International Investment Corporation, Robert S. Folsom, Margaret D.
Folsom, R. Stephen Folsom, Robert T. Hayes, Cynthia Ann Hayes, Alicia Ellen
Hayes, Joann Hayes, William C. Saunders, William C. Kennedy, Jr., Donald M.
Kennedy, Mark D. Ein and The Erin Mills Investment Corporation.

                                      B-2
<PAGE>
 
                                                                      Appendix C

                                 Former Parties

Margaret D. Folsom
R. Stephen Folsom
Joann Hayes
Cynthia Ann Hayes
Alicia Ellen Hayes

                                      C-1
<PAGE>
 
                                                                      Appendix D

<TABLE> 
<CAPTION> 

Certain Stockholders                        Number of Shares

<S>                                                <C>
Erin Mills International Investment Corporation    8,141,706
William C. Kennedy, Jr.                            2,029,318
Carlyle-HighwayMaster Investors, L.P.              1,805,727
William C. Saunders                                  892,015
Clipper/Merban, L.P.                                 530,930
Clipper/Merchant Partners, L.P.                      524,209
H.M. Rana Investments Limited                        423,802
T.C. Group, L.L.C.                                   291,315
Robert S. Folsom                                     280,000
Carlyle-HighwayMaster Investors II, L.P.             170,071
</TABLE>

                                      D-1

<PAGE>
 
                               IRREVOCABLE PROXY

          The undersigned stockholder of HighwayMaster Communications, Inc., a
Delaware corporation (the "Company"), hereby irrevocably (to the fullest extent
provided by law) appoints Southwestern Bell Wireless Holdings, Inc., a Delaware
corporation ("SBW"), or its nominee, the attorney and proxy of the undersigned,
with full power of substitution and resubstitution, to the full extent of the
undersigned's rights with respect to the 1,805,727 shares of Common Stock, par
value $0.01 per share ("Common Stock"), of the Company owned beneficially or of
record by the undersigned (the "Shares"), and any and all other shares or
securities issued or issuable in respect thereof on or after the date hereof, to
exercise the voting and other rights specified below in accordance with the
provisions and subject to the limitations set forth herein.  Upon the execution
hereof, all prior proxies given by the undersigned with respect to the Shares
and any and all other shares or securities issued or issuable in respect thereof
on or after the date hereof as to matters covered hereby are hereby revoked and
no subsequent proxies will be given as to the matters covered hereby.  This
proxy is irrevocable (to the fullest extent provided by law), coupled with an
interest, and is granted in connection with the Amended and Restated
Stockholders' Agreement, dated the date hereof, among the Company and the
stockholders party thereto, including the undersigned stockholder (the
"Stockholders' Agreement"), and is granted in consideration of SBW entering into
the Purchase Agreement, dated the date hereof (the "Purchase Agreement"),
between the Company and SBW.

          The attorney and proxy named above will be empowered to exercise all
voting and other rights (including, without limitation, the power to execute and
deliver written consents with respect to the Shares) of the undersigned at every
annual, special or adjourned meeting of stockholders of the Company and in every
written consent in lieu of such a meeting, or otherwise, (i) in favor of
approval of the adoption of the Certificate of Amendment attached hereto as
Exhibit A (the "Certificate of Amendment"), (ii) in favor or the approval of the
issuance by the Company to SBW of shares of Common Stock upon the exercise of
the Warrants to purchase an aggregate of up to 5,000,000 shares of Common Stock
evidenced by the Warrant Certificate, dated the date hereof, executed by the
Company in favor of SBW and (iii) against any action or agreement that, directly
or indirectly, is inconsistent with or that is reasonably likely to impede,
interfere with, delay or postpone the transactions referred to in clause (i) or
(ii) above.

          The attorney and proxy named above may only exercise this proxy to
vote the Shares subject hereto at any annual, special or adjourned meeting of
the stockholders of the Company, and in any written consent in lieu of such
meeting, with respect to the matters specified in clauses (i), (ii) and (iii) of
the immediately preceding paragraph, and may not exercise this proxy in respect
of any other matter.  The undersigned stockholder may vote the Shares (or grant
one or more proxies to vote the Shares) on all other matters.

          Any obligation of the undersigned hereunder shall be binding upon the
successors and assigns of the undersigned.
<PAGE>
 
          The undersigned stockholder shall perform such further acts and
execute such further documents as may reasonably be required to vest in SBW the
power to vote the Shares in accordance with the provisions and subject to the
limitations set forth herein and to otherwise carry out the provisions of this
proxy.

          This power of attorney and proxy shall terminate upon the earlier of
the filing of the Certificate of Amendment with the Secretary of State of the
State of Delaware and the termination of the Purchase Agreement pursuant to
Section 2 thereof.

Dated:  September 30, 1996      STOCKHOLDER:

                                CARLYLE-HIGHWAYMASTER INVESTORS, L.P.
                                By:     TC Group, L.L.C.
                                        Its General Partner

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

                                                                               2
<PAGE>
 
                               IRREVOCABLE PROXY

          The undersigned stockholder of HighwayMaster Communications, Inc., a
Delaware corporation (the "Company"), hereby irrevocably (to the fullest extent
provided by law) appoints Southwestern Bell Wireless Holdings, Inc., a Delaware
corporation ("SBW"), or its nominee, the attorney and proxy of the undersigned,
with full power of substitution and resubstitution, to the full extent of the
undersigned's rights with respect to the 170,071 shares of Common Stock, par
value $0.01 per share ("Common Stock"), of the Company owned beneficially or of
record by the undersigned (the "Shares"), and any and all other shares or
securities issued or issuable in respect thereof on or after the date hereof, to
exercise the voting and other rights specified below in accordance with the
provisions and subject to the limitations set forth herein.  Upon the execution
hereof, all prior proxies given by the undersigned with respect to the Shares
and any and all other shares or securities issued or issuable in respect thereof
on or after the date hereof as to matters covered hereby are hereby revoked and
no subsequent proxies will be given as to the matters covered hereby.  This
proxy is irrevocable (to the fullest extent provided by law), coupled with an
interest, and is granted in connection with the Amended and Restated
Stockholders' Agreement, dated the date hereof, among the Company and the
stockholders party thereto, including the undersigned stockholder (the
"Stockholders' Agreement"), and is granted in consideration of SBW entering into
the Purchase Agreement, dated the date hereof (the "Purchase Agreement"),
between the Company and SBW.

          The attorney and proxy named above will be empowered to exercise all
voting and other rights (including, without limitation, the power to execute and
deliver written consents with respect to the Shares) of the undersigned at every
annual, special or adjourned meeting of stockholders of the Company and in every
written consent in lieu of such a meeting, or otherwise, (i) in favor of
approval of the adoption of the Certificate of Amendment attached hereto as
Exhibit A (the "Certificate of Amendment"), (ii) in favor or the approval of the
issuance by the Company to SBW of shares of Common Stock upon the exercise of
the Warrants to purchase an aggregate of up to 5,000,000 shares of Common Stock
evidenced by the Warrant Certificate, dated the date hereof, executed by the
Company in favor of SBW and (iii) against any action or agreement that, directly
or indirectly, is inconsistent with or that is reasonably likely to impede,
interfere with, delay or postpone the transactions referred to in clause (i) or
(ii) above.

          The attorney and proxy named above may only exercise this proxy to
vote the Shares subject hereto at any annual, special or adjourned meeting of
the stockholders of the Company, and in any written consent in lieu of such
meeting, with respect to the matters specified in clauses (i), (ii) and (iii) of
the immediately preceding paragraph, and may not exercise this proxy in respect
of any other matter.  The undersigned stockholder may vote the Shares (or grant
one or more proxies to vote the Shares) on all other matters.

          Any obligation of the undersigned hereunder shall be binding upon the
successors and assigns of the undersigned.

                                                                               3
<PAGE>
 
          The undersigned stockholder shall perform such further acts and
execute such further documents as may reasonably be required to vest in SBW the
power to vote the Shares in accordance with the provisions and subject to the
limitations set forth herein and to otherwise carry out the provisions of this
proxy.

          This power of attorney and proxy shall terminate upon the earlier of
the filing of the Certificate of Amendment with the Secretary of State of the
State of Delaware and the termination of the Purchase Agreement pursuant to
Section 2 thereof.

Dated:  September 30, 1996      STOCKHOLDER:

                                CARLYLE-HIGHWAYMASTER INVESTORS II, L.P.
                                By:     TC Group, L.L.C.
                                        Its General Partner

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

                                                                               4
<PAGE>
 
                               IRREVOCABLE PROXY

          The undersigned stockholder of HighwayMaster Communications, Inc., a
Delaware corporation (the "Company"), hereby irrevocably (to the fullest extent
provided by law) appoints Southwestern Bell Wireless Holdings, Inc., a Delaware
corporation ("SBW"), or its nominee, the attorney and proxy of the undersigned,
with full power of substitution and resubstitution, to the full extent of the
undersigned's rights with respect to the 291,315 shares of Common Stock, par
value $0.01 per share ("Common Stock"), of the Company owned beneficially or of
record by the undersigned (the "Shares"), and any and all other shares or
securities issued or issuable in respect thereof on or after the date hereof, to
exercise the voting and other rights specified below in accordance with the
provisions and subject to the limitations set forth herein.  Upon the execution
hereof, all prior proxies given by the undersigned with respect to the Shares
and any and all other shares or securities issued or issuable in respect thereof
on or after the date hereof as to matters covered hereby are hereby revoked and
no subsequent proxies will be given as to the matters covered hereby.  This
proxy is irrevocable (to the fullest extent provided by law), coupled with an
interest, and is granted in connection with the Amended and Restated
Stockholders' Agreement, dated the date hereof, among the Company and the
stockholders party thereto, including the undersigned stockholder (the
"Stockholders' Agreement"), and is granted in consideration of SBW entering into
the Purchase Agreement, dated the date hereof (the "Purchase Agreement"),
between the Company and SBW.

          The attorney and proxy named above will be empowered to exercise all
voting and other rights (including, without limitation, the power to execute and
deliver written consents with respect to the Shares) of the undersigned at every
annual, special or adjourned meeting of stockholders of the Company and in every
written consent in lieu of such a meeting, or otherwise, (i) in favor of
approval of the adoption of the Certificate of Amendment attached hereto as
Exhibit A (the "Certificate of Amendment"), (ii) in favor or the approval of the
issuance by the Company to SBW of shares of Common Stock upon the exercise of
the Warrants to purchase an aggregate of up to 5,000,000 shares of Common Stock
evidenced by the Warrant Certificate, dated the date hereof, executed by the
Company in favor of SBW and (iii) against any action or agreement that, directly
or indirectly, is inconsistent with or that is reasonably likely to impede,
interfere with, delay or postpone the transactions referred to in clause (i) or
(ii) above.

          The attorney and proxy named above may only exercise this proxy to
vote the Shares subject hereto at any annual, special or adjourned meeting of
the stockholders of the Company, and in any written consent in lieu of such
meeting, with respect to the matters specified in clauses (i), (ii) and (iii) of
the immediately preceding paragraph, and may not exercise this proxy in respect
of any other matter.  The undersigned stockholder may vote the Shares (or grant
one or more proxies to vote the Shares) on all other matters.

          Any obligation of the undersigned hereunder shall be binding upon the
successors and assigns of the undersigned.

                                                                               5
<PAGE>
 
          The undersigned stockholder shall perform such further acts and
execute such further documents as may reasonably be required to vest in SBW the
power to vote the Shares in accordance with the provisions and subject to the
limitations set forth herein and to otherwise carry out the provisions of this
proxy.

          This power of attorney and proxy shall terminate upon the earlier of
the filing of the Certificate of Amendment with the Secretary of State of the
State of Delaware and the termination of the Purchase Agreement pursuant to
Section 2 thereof.

Dated:  September 30, 1996      STOCKHOLDER:

                                TC Group, L.L.C.

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

                                                                               6


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