1 EXHIBIT 4.4 - -------------------------------------------------------------------------------- WARRANT AGREEMENT BETWEEN ADMINISTAFF, INC. AND AMERICAN EXPRESS TRAVEL RELATED SERVICES COMPANY, INC. Dated as of March 10, 1998 - -------------------------------------------------------------------------------- 2 WARRANT AGREEMENT THIS WARRANT AGREEMENT is made as of March 10, 1998, by and between ADMINISTAFF, INC., a Delaware corporation (the "Company"), and AMERICAN EXPRESS TRAVEL RELATED SERVICES COMPANY, INC., a New York corporation (the "Purchaser"). RECITALS: A. The Company and the Purchaser have entered into a Securities Purchase Agreement dated as of January 27, 1998 (the "Purchase Agreement"), pursuant to which the Purchaser has agreed to purchase from the Company 693,126 Units (as hereinafter defined), each of which shall consist of one share of Common Stock (as hereinafter defined) and 2.98 Warrants (as hereinafter defined). B. The Company and the Purchaser have agreed to enter into this Agreement to supplement the terms and conditions set forth in the Purchase Agreement which relate to the Warrants purchased thereunder. NOW, THEREFORE, the parties hereto agree as follows: SECTION 1. Definitions. (a) Certain Definitions. For the purposes of this Agreement, the following terms have the meanings set forth below: "Affiliate" has the same meaning as in Rule 12b-2 promulgated under the Exchange Act. "Business Day" means any day which is neither a Saturday or Sunday nor a legal holiday on which banks are authorized or required to be closed in New York, New York or Houston, Texas. "Change of Control" means the occurrence of any of the following: (a) any third party shall have acquired beneficial ownership of more than 30% of the outstanding voting stock of the Company (within the meaning of Section 13(d) or 14(d) of the Exchange Act); or (b) individuals who on the Closing Date were directors of the Company (together with any replacement or additional directors who were nominated or elected by a majority of directors then in office) cease to constitute a majority of the Board of Directors of the Company. "Closing Date" means March 10, the date of the Closing of the purchase by the Purchaser of the Units in accordance with the Purchase Agreement. 3 "Common Stock" means shares now or hereafter authorized of any class of common stock of the Company and any other class of capital stock of the Company, however designated, that has the right (subject to any prior rights of any class or series of preferred stock) to participate in any distribution of the assets upon voluntary or involuntary liquidation, dissolution or winding up of the Company or in the earnings of the Company without limit as to per share amount, and shall include, without limitation, the presently authorized 60,000,000 shares of Common Stock, par value $0.01 per share. "Company" is defined in the Preamble. "Exchange Act" means the Securities Exchange Act of 1934, as amended. "Expiration Date" is defined in the Warrant Certificates. "Exercise Price" means the exercise price per Warrant as set forth in the Warrant Certificate evidencing such Warrant and as adjusted from time to time in accordance with this Agreement. "Fair Market Value per Share" means the arithmetic mean of the closing sales price of a share of Common Stock of the Company as reported by the New York Stock Exchange Composite Transactions over the five trading days immediately preceding the date of determination or, if not so trading, the fair value as determined in good faith by the Board of Directors of the Company. "GAAP" means generally accepted accounting principles in effect from time to time in the United States. "Governmental Authority" means any nation or government, any state or other political subdivision thereof and any entity exercising executive, legislative, judicial, regulatory or administrative functions of or pertaining to government. "Holder" means the Purchaser or any subsequent holder of Warrants or Warrant Stock, to which the Warrants or Warrant Stock are transferred in accordance with the provisions of this Agreement and the Purchase Agreement. "Marketing Agreement" means the Marketing Agreement, dated as of the date hereof, by and between the Company and the Purchaser in substantially the form of Exhibit A attached to the Purchase Agreement. "Person" means any natural person, corporation, partnership, limited liability company, firm, association or any other entity, whether acting in an individual, fiduciary or other capacity. "Purchase Agreement" is defined in the Recitals. -2- 4 "Put Closing" is defined in Section 5(a). "Put Exercise Notice" is defined in Section 5(a). "Put Price" is defined in Section 5(a). "Put Right" is defined in Section 5(a). "Registration Rights Agreement" means the Registration Rights Agreement, dated as of the date hereof, between the Company and the Purchaser, in substantially the form of Exhibit B attached to the Purchase Agreement. "SEC" means the Securities and Exchange Commission. "Securities Act" means the Securities Act of 1933, as amended. "Unit" means an investment unit consisting of one share of Common Stock and 2.98 Warrants. "Warrant Certificates" means collectively, the certificates evidencing (i) the Warrants with an Expiration Date of the third anniversary of the Closing Date in the form of Exhibit A-1 attached hereto, (ii) the Warrants with an Expiration Date of the fourth anniversary of the Closing Date in the form of Exhibit A-2 attached hereto, (iii) the Warrants with an Expiration Date of the fifth anniversary of the Closing Date in the form of Exhibit A-3 attached hereto, (iv) the Warrants with an Expiration Date of the sixth anniversary of the Closing Date in the form of Exhibit A-4 attached hereto, (v) the Warrants with an Expiration Date of the seventh anniversary of the Closing Date in the form of Exhibit A-5 attached hereto. "Warrant Stock" means the securities which a Holder may acquire upon exercise of a Warrant, together with any other securities which such Holder may be issued in respect of any such securities, including, without limitation, by way of any dividend or other distribution on such securities, any split-up of such securities or a recapitalization, merger, consolidation, share exchange, reorganization or other transaction or series of related transactions in which shares of such securities are changed into or exchanged for securities of another corporation. "Warrants" means the 2,065,515 warrants each of which entitles the holder thereof to purchase one share of Common Stock of the Company issued to the Purchaser on the Closing Date pursuant to this Agreement and the Purchase Agreement, which warrants shall be subject to adjustment and shall have the rights, privileges and limitations set forth in this Agreement and in each Warrant. -3- 5 (b) Terms Defined in Purchase Agreement. Unless otherwise defined herein, capitalized terms used in this Agreement shall have the meanings ascribed to such terms in the Purchase Agreement. SECTION 2. Exercise of Warrants. (a) A Warrant may be exercised by the Purchaser or any Holder only in accordance with the terms and conditions of this Agreement and at any time during the period beginning on the date hereof and ending on the Expiration Date for such Warrant as set forth in the Warrant Certificate evidencing such Warrant. The Warrant Certificates evidencing the Warrants issued to the Purchaser on the Closing Date shall be identical except for the Expiration Date and the Exercise Price. The Expiration Date for the Warrants shall be as follows: the third anniversary of the Closing Date for 400,000 Warrants; the fourth anniversary of the Closing Date for 400,000 Warrants; the fifth anniversary of the Closing Date for 400,000 Warrants; the sixth anniversary of the Closing Date for 400,000 Warrants; and the seventh anniversary of the Closing Date for 465,515 Warrants. The Exercise Price for the Warrants shall be as follows: $40 for the Warrants expiring on the third anniversary of the Closing Date; $50 for the Warrants expiring on the fourth anniversary of the Closing Date; $60 for the Warrants expiring on the fifth anniversary of the Closing Date; $70 for the Warrants expiring on the sixth anniversary of the Closing Date; and $80 for the Warrants expiring on the seventh anniversary of the Closing Date. (b) Subject to the terms and conditions hereof, Warrants may be exercised pursuant to this Section 2 upon surrender to the Company at its office designated for such purpose (the address of which is set forth in Section 13) of the certificate or certificates evidencing the Warrant(s) to be exercised and upon payment to the Company of the aggregate Exercise Price for the number of Warrants which are then exercised, provided that a Warrant may not be exercised in part. Upon such surrender of Warrant Certificates and payment of the Exercise Price in cash or by check payable to the Company, the Company shall issue and cause to be delivered with all reasonable dispatch (and in any event within three Business Days after such surrender) to or upon the written order of the Holder, and in the name of the Holder or the Holder's nominee, a certificate or certificates for the number of full shares of Warrant Stock issuable upon the exercise of such Warrants, together with such other property (including cash) and securities as may then be deliverable upon such exercise, including cash for fractional Warrant Stock as provided in Section 11, provided that all such Warrant Stock held by the Purchaser shall be subject to the restrictions set forth in Sections 7 and 8 of the Purchase Agreement. Such certificate or certificates shall be deemed to have been issued and the Person so named therein shall be deemed to have become a holder of record of such Warrant Stock as of the date of the surrender of such Warrant Certificates. -4- 6 (c) Subject to the terms and conditions hereof, the Warrants shall be exercisable at the election of the Holders thereof, either in full or from time to time in part (but in no event shall a Warrant be exercisable in part), and in the event that a Warrant Certificate is exercised in respect of fewer than all of the Warrants evidenced by such Warrant Certificate at any time prior to the Expiration Date of such Warrant, a new Warrant Certificate evidencing the remaining Warrant or Warrants will be issued and delivered pursuant to the provisions of this Section 2(c). All Warrant Certificates surrendered upon exercise of Warrants shall be canceled. The Company shall keep copies of this Agreement and any notices received hereunder available for inspection during normal business hours at its office. The Company will furnish, at its expense, copies of this Agreement and all such notices, upon request, to any Holder of any Warrant Certificates. SECTION 3. Adjustment of Exercise Price and Number of Shares of Warrant Stock Issuable. The Exercise Price and the number of shares of Warrant Stock issuable upon the exercise of each Warrant are subject to adjustment from time to time upon the occurrence of any of the events enumerated in this Section 3. (a) Adjustment for Change in Capital Stock of the Company. If the Company (i) pays a dividend or makes a distribution on its Common Stock in shares of any class of its capital stock, (ii) subdivides its outstanding shares of Common Stock into a greater number of shares, (iii) combines its outstanding shares of Common Stock into a smaller number of shares, (iv) makes a distribution on its Common Stock in shares of its capital stock other than Common Stock, or (v) issues to holders of its Common Stock by reclassification of its Common Stock any shares of its capital stock, then the Exercise Price and number of shares for which any Warrant may be exercised in effect immediately prior to such action shall be proportionately adjusted so that the Holder of the Warrant thereafter exercised may receive the aggregate number and kind of shares of capital stock of the Company which it would have owned immediately following such action if such Warrant had been exercised immediately prior to such action. Such adjustment shall be made successively whenever any event listed above shall occur, and shall become effective immediately after the record date in the case of a dividend or distribution and immediately after the effective date in the case of a subdivision, combination or reclassification. If after an adjustment made pursuant to the second preceding sentence a Holder of a Warrant upon exercise of such Warrant may receive shares of two or more classes of capital stock of the Company, the Board of Directors of the Company shall determine in the good faith exercise of its reasonable business judgment the allocation of the adjusted Exercise Price between the classes of capital stock. After such allocation, the exercise privilege and the Exercise Price of each class of capital stock shall thereafter be subject to adjustment on terms comparable to those in this Section 3. (b) Reorganization of the Company. In the event of any capital reorganization, recapitalization or reclassification of the capital stock of the Company, or consolidation or merger of the Company with another entity, in which the Company does not continue as the surviving corporation or, if it does so continue, its Common Stock does not remain outstanding, any acquisition of capital stock of the Company by means of a share exchange, or the sale, lease, transfer, conveyance or other disposition of all or substantially all of its assets to another entity, then, as a -5- 7 condition of and concurrently with such reorganization, recapitalization, reclassification, consolidation, merger, share exchange or sale, lease, transfer, conveyance or other disposition, lawful and adequate provision shall be made whereby the Holders of the Warrant Certificates shall thereafter have the right to purchase and receive, on the basis and upon the terms and conditions specified in this Agreement and in lieu of the Warrant Stock immediately theretofore purchasable and receivable upon the exercise of the rights represented by the Warrants, such shares of stock, securities, cash or property as would have been issued or payable with respect to or in exchange for the number of shares of Warrant Stock purchasable and receivable immediately prior to such transaction upon the exercise of the rights represented by the Warrant Certificates if such Warrants had been exercised immediately prior to such transaction. If such consolidation, merger, share exchange, sale, lease, transfer, conveyance or other disposition is with any Person or group of Persons (within the meaning of Section 13(d) or 14(d) of the Exchange Act) who shall have made a purchase, tender or exchange offer pursuant to which a majority of the outstanding shares of Common Stock of the Company were validly tendered and accepted, promptly after the consummation of such transaction, the Holders of the Warrants shall be given a reasonable opportunity (and, in no event, less than 30 days) to elect to receive the stock, securities, cash or property issued or paid (or to be issued or paid) to holders of the Common Stock in accordance with such offer. In any such case appropriate provision shall be made with respect to the rights and interests of the Holders of the Warrants to the end that the provisions of this Agreement (including, without limitation, provisions for adjustment of the Exercise Price and of the number and type of securities purchasable upon the exercise of the Warrants) shall thereafter be applicable, as nearly as may be, in relation to any shares of stock, securities, cash or property thereafter deliverable upon the exercise of the Warrants. The Company shall not effect any such consolidation, merger, share exchange or sale, lease, transfer, conveyance or other disposition unless prior to or simultaneously with the consummation thereof the successor entity (if other than the Company) resulting from such consolidation, merger or share exchange or the entity purchasing or otherwise acquiring such assets or shares (i) shall assume by a supplemental Warrant Agreement, reasonably satisfactory in form, scope and substance to the Holders (which shall be mailed or delivered to the Holders of the Warrants at the last address of such Holders appearing on the books of the Company) the obligation to deliver to such Holders such shares of stock, securities, cash or property as, in accordance with the foregoing provisions, such Holders may be entitled to purchase (the "Substitute Securities") and (ii) shall assume all of the other obligations of the Company set forth in this Agreement, the Purchase Agreement and the Registration Rights Agreement. Following such assumption such obligations shall apply to the Substitute Securities rather than to the Warrant Stock. If the issuer of securities deliverable upon exercise of Warrants under the supplemental Warrant Agreement is an Affiliate of the formed, surviving, transferee or lessee entity, such issuer shall join the supplemental Warrant Agreement. The foregoing provisions of this paragraph shall similarly apply to successive reorganizations, recapitalizations, reclassifications, consolidations, mergers, share exchanges, sales, leases, transfers, conveyances or other dispositions. -6- 8 SECTION 4. Covenants. (a) Private Company Information. If the Company shall cease to be subject to the periodic reporting obligations of the Exchange Act and for so long as the Purchaser's Interest is at least five percent, the Company will furnish, or will cause to be furnished, to each Holder copies of the following financial statements, reports and information: (i) promptly when available and in any event within 90 days after the close of each Fiscal Year, a consolidated balance sheet at the close of such Fiscal Year, and related consolidated statements of operations, stockholders' equity and cash flows for such Fiscal Year, of the Company and the Company Subsidiaries (with comparable information at the close of and for the prior Fiscal Year), certified (in the case of consolidated statements) without qualification by Ernst & Young or other nationally recognized independent public accountants; and (ii) promptly when available and in any event within 45 days after the close of each Fiscal Quarter, consolidated balance sheets at the close of such Fiscal Quarter, and consolidated statements of operations, stockholders' equity and cash flows for such Fiscal Quarter and for the period commencing at the close of the previous Fiscal Year and ending with the close of such Fiscal Quarter, of the Company and the Company Subsidiaries (with comparable information at the close of and for the corresponding Fiscal Quarter of the prior Fiscal Year and for the corresponding portion of such prior Fiscal Year), certified by the chief financial or executive officer of the Company. (b) Public Company Information. So long as the Company is subject to the periodic reporting requirements of the Exchange Act and for so long as the Purchaser's Interest is at least five percent, the Company will: (i) file with the SEC on or before the required date all regular or periodic reports required pursuant to the Exchange Act; and (ii) use its reasonable commercial efforts to make publicly available information concerning the Company sufficient to allow a Holder to dispose in accordance with this Agreement and the Warrant Agreement of all or a portion of the Warrant Stock pursuant to Rule 144 (or any successor provision) promulgated by the SEC under the Securities Act. (c) Inconsistent Agreements. The Company will not, and will not permit any Company Subsidiary to, take any action which would (i) impair or adversely affect the right of a Holder to exercise the Warrants or (ii) breach any of the covenants or agreements in this document. -7- 9 (d) Governmental Approvals. The Company will use its reasonable commercial efforts, and will cooperate with the Holders to, secure all necessary consents, approvals, authorizations and exemptions from all Governmental Authorities in connection with the transactions contemplated hereby and the exercise of the Warrants and the issuance of shares of Common Stock upon exercise of the Warrants. (e) Termination of Rights upon Sale to the Public. Notwithstanding anything to the contrary set forth herein, the obligations of the Company set forth in this Section 4 shall terminate with respect to any Holder (including an underwriter) acquiring any Warrants or Warrant Stock pursuant to a registration statement declared effective by the SEC under the Securities Act or in a sale effected pursuant to Rule 144 promulgated under the Securities Act. SECTION 5. Restrictions on Transfers. (a) Transfers of Warrants. (i) Without the prior written consent of the Company, the Purchaser may not dispose of or transfer any Warrants now or hereafter owned, whether by sale, assignment, gift, pledge, encumbrance or otherwise, except (A) to a Subsidiary of the Purchaser or to any entity of which the Purchaser is, directly or indirectly, a Subsidiary (provided that such transferee agrees to be bound by the transfer restrictions contained herein), (B) in connection with the exercise of a Warrant in accordance with the provisions of the Agreement and (C) in connection with the exercise in accordance with Section 5(a)(ii) of a put of a Warrant to the Company after the occurrence of a Change of Control. (ii) Upon a Change of Control, each of the Purchaser and any other Holders to which the Warrants were transferred in accordance with Section 5(a) hereof shall individually have the right (the "Put Right") to require the Company to purchase all (but not less than all) of the Warrants owned by the Purchaser and each such Holder. The Company shall notify each Holder in writing, as promptly as practicable, but in any event within three Business Days, after a Change in Control. The Put Right may be exercised by the Purchaser and any Holder by delivering a written notice, which notice shall be irrevocable (the "Put Exercise Notice"), to the Company within 90 days after any Change of Control. The purchase price for each Warrant purchased by the Company upon exercise of the Put Right shall equal the Fair Market Value per Share as of the date of the Change of Control minus the Exercise Price of such Warrant (the "Put Price"). The purchase and sale of the Warrants upon exercise of the Put Rights shall be consummated at a closing (the "Put Closing") that shall occur not later than 15 days following the Put Exercise Notice. At the Put Closing, the Purchaser and the Holders seeking to exercise the Put Rights set forth herein shall surrender to the Company the Warrant Certificates evidencing their Warrants. In exchange therefor, (A) if the Put Price for the Warrants evidenced -8- 10 by a Warrant Certificate is greater than zero, the Company shall issue to the Holder of such Warrants Common Stock in an amount, calculated based on the Fair Market Value per Share of such Common Stock at the time of Change of Control, equal to the Put Price for such Warrants multiplied by the number of Warrants evidenced by such Warrant Certificate and (B) if the Put Price for the Warrants evidenced by a Warrant Certificate is not greater than zero, the Company shall not be obligated to make any payment or issue any Common Stock to the Holder of such Warrants. Prior to the delivery of a Put Exercise Notice, the Put Right shall not restrict or limit or have any affect on a Holder's right to exercise a Warrant pursuant to Section 2 hereof. If as a result of a Change in Control the Company is not the surviving entity or shares of Common Stock are no longer outstanding after a Change in Control, then the Put Price shall be payable in such shares of stock, securities, cash or property as would have been issued or payable as a result of such Change of Control with respect to or in exchange for the number of shares of Common Stock a Holder would have received upon exercise of the Put immediately prior to such Change in Control. (b) Restricted Securities. Warrants are transferable only in accordance with Section 5(a). (c) Transfers of Warrant Stock. The Purchaser may not dispose of or transfer any Warrant Stock now or hereafter owned, whether by sale, assignment, gift, pledge, encumbrance or otherwise, except in accordance with Section 8 of the Purchase Agreement. SECTION 6. Termination. This Agreement shall terminate on the earlier of (a) the seventh anniversary of the Closing Date and (b) the exercise or expiration of all Warrants issued pursuant to this Agreement. Each Warrant shall expire upon the Expiration Date set forth in the Warrant Certificate by which it is evidenced. SECTION 7. Registration of Transfers and Exchanges. (a) The Company shall from time to time register the transfer of any outstanding Warrant Certificates made in accordance with Section 5 hereof in a Warrant register to be maintained by the Company upon surrender of such Warrant Certificates accompanied by a written instrument or instruments of transfer in form reasonably satisfactory to the Company, duly executed by the Holder or Holders thereof or by the duly appointed legal representative thereof or by a duly authorized attorney; provided, however, that prior to effecting such transfer, the transferee shall agree (in a form reasonably satisfactory to the Company) to be bound by the terms of this Agreement. Upon any such registration of transfer, a new Warrant Certificate shall be issued to the transferee(s) and the surrendered Warrant Certificate shall be canceled. Until the Warrant Certificate is transferred on the Warrant register of the Company, the Company may treat the Holder as shown in the Warrant register as the absolute owner of the Warrant Certificate for all purposes, and -9- 11 notwithstanding any notice to the contrary. The Company agrees that it will make the Warrant register available for inspection by the Holders for a proper purpose during normal business hours at its office. (b) The Holders agree that each Warrant Certificate and each certificate representing Warrant Stock will bear the following legend (the "Securities Legend"): "THE SECURITIES REPRESENTED BY THIS CERTIFICATE HAVE NOT BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933, AS AMENDED, OR ANY STATE SECURITIES LAWS. SAID SECURITIES MAY NOT BE SOLD OR TRANSFERRED IN THE ABSENCE OF SUCH REGISTRATION OR AN EXEMPTION FROM THE REGISTRATION PROVISIONS OF SAID ACT OR LAWS. THE SECURITIES REPRESENTED BY THIS CERTIFICATE ARE SUBJECT TO THE TERMS OF A SECURITIES PURCHASE AGREEMENT, DATED AS OF JANUARY 27, 1998, BETWEEN ADMINISTAFF, INC. (THE "COMPANY") AND AMERICAN EXPRESS TRAVEL RELATED SERVICES COMPANY, INC. (THE "PURCHASER"), A WARRANT AGREEMENT DATED AS OF MARCH __ 1998, BETWEEN THE COMPANY AND THE PURCHASER, AND A REGISTRATION RIGHTS AGREEMENT, DATED AS OF MARCH __ 1998, BETWEEN THE COMPANY AND THE PURCHASER, COPIES OF EACH OF WHICH ARE ON FILE AT THE MAIN OFFICE OF THE COMPANY. ANY SALE OR TRANSFER OF THE SECURITIES EVIDENCED BY THIS CERTIFICATE IS SUBJECT TO THE TERMS OF THOSE AGREEMENTS AND ANY SALE OR TRANSFER OF SUCH SECURITIES IN VIOLATION OF SAID AGREEMENTS SHALL BE INVALID." (c) If the holder of the Warrants or Warrant Stock delivers, in accordance with Section 8(e) of the Purchase Agreement, to the Company an opinion of King & Spalding or such other counsel that no subsequent transfer of such Warrants or Warrant Stock shall require registration under the Securities Act, the Company shall promptly upon such contemplated transfer deliver new certificates for such Warrants or Warrant Stock which do not bear the Securities Legend; -10- 12 provided, however, that if at such time, any such Warrants or Warrant Stock remain subject to certain provisions of this Agreement or the Purchase Agreement, the Company shall not remove the Securities Legend, but shall modify it to delete all references to restrictions or conditions on sale of Warrants or Warrant Stock except those references to restrictions or conditions which are specified in this Agreement or the Purchase Agreement. If the Company is not required to deliver new certificates for such Warrants or Warrant Stock not bearing such legend, the holder thereof shall not transfer the same until the prospective transferee has confirmed to the Company in writing its agreement to be bound by the conditions contained in Section 5(b) hereof with respect to Warrants and Section 8(b) of the Purchase Agreement with respect to Warrant Stock. (d) If any Warrants or Warrant Stock are or become eligible for sale pursuant to Rule 144(k), the Company, upon the request of holders of any such Warrants or Warrant Stock, shall remove the Securities Legend from the certificates for such Warrants or Warrant Stock; provided, however, that if at such time, any such Warrants or Warrant Stock remain subject to certain provisions of this Agreement or the Purchase Agreement, the Company shall not remove the Securities Legend, but shall modify it to delete all references to restrictions or conditions on sale of the Warrants or Warrant Stock except those references to restrictions or conditions which are still applicable and specified in this Agreement or the Purchase Agreement. (e) Warrant Certificates may be exchanged at the option of the Holder(s) thereof when surrendered to the Company at its office for another Warrant Certificate or other Warrant Certificates of like tenor and representing in the aggregate a like number of Warrants, including, without limitation, upon an adjustment in the Exercise Price or in the number of Warrant Shares purchasable upon exercise of the Warrants. Warrant Certificates surrendered for exchange shall be canceled. SECTION 8. Payment of Taxes. The Company will pay all stamp, transfer and similar taxes in connection with the issuance, sale and delivery of the Warrants hereunder, as well as all such taxes attributable to the initial issuance of Warrant Stock upon the exercise of Warrants and payment of the appropriate Exercise Price. The Company will not, however, be required to pay any such taxes imposed in connection with any transfer of any Warrants or Warrant Stock or any federal or state income taxes payable in respect of any Holder's purchase, ownership, sale, transfer, exercise or other disposition of Warrants or Warrant Stock. SECTION 9. Mutilated or Missing Warrant Certificates. Upon receipt by the Company of evidence reasonably satisfactory to the Company (which shall include an affidavit of the Holder) that any Warrant Certificate shall have been mutilated, lost, stolen or destroyed and, in the case of loss, theft or destruction, a customary indemnity agreement from the Holder of such Warrant Certificate, the Company shall issue, in exchange and substitution for and upon cancellation of the mutilated Warrant Certificate, or in lieu of and substitution for the Warrant Certificate lost, stolen or destroyed, a new Warrant Certificate of like tenor and representing an equivalent number of Warrants. -11- 13 SECTION 10. Reservation of Warrant Stock. The Company will at all times that any Warrant is exercisable reserve and keep available, free from preemptive or similar rights, out of the aggregate of its authorized but unissued capital stock or its authorized and issued capital stock held in its treasury, for the purpose of enabling it to satisfy any obligation to issue Warrant Stock upon exercise of Warrants, the maximum number of shares of each class of capital stock constituting a part of the Warrant Stock which may then be deliverable upon the exercise of all outstanding Warrants. The Company or, if appointed, the transfer agent for shares of each class of capital stock of the Company (the "Transfer Agent") and every subsequent transfer agent for any shares of the Company's capital stock issuable upon the exercise of the Warrants will be irrevocably authorized and directed at all times to reserve such number of authorized shares as shall be required for such purpose. The Company will keep a copy of this Agreement on file with the Transfer Agent and with every subsequent transfer agent for any shares of the Company's capital stock issuable upon the exercise of the rights of purchase represented by the Warrants. The Company will furnish such Transfer Agent a copy of all notices of adjustments, and certificates related thereto, transmitted to Holders pursuant to Section 12. Before taking any action which would cause an adjustment pursuant to Section 3 to the maximum number of shares of Warrant Stock deliverable upon the exercise of all outstanding Warrants pursuant to Section 2(a), the Company shall cause to be authorized additional shares of Common Stock such that the sum of such maximum number of shares of Common Stock deliverable upon exercise of all outstanding Warrants and the number of shares of Common Stock outstanding or issuable pursuant to outstanding rights, options or warrants as of such date does not exceed the number of shares of Common Stock authorized pursuant to the Company's Certificate. SECTION 11. Fractional Interests. The Company shall not be required to issue fractional shares of Warrant Stock on the exercise of Warrants. If more than one Warrant shall be presented for exercise in full at the same time by the same Holder, the number of full shares of Warrant Stock which shall be issuable upon exercise thereof shall be computed on the basis of the aggregate number of shares of Warrant Stock purchasable on exercise of the Warrants so presented. If any fraction of a share of the Warrant Stock would, except for the provisions of this Section 11, be issuable on the exercise of any Warrants (or specified portion thereof), the Company shall pay an amount in cash equal to the Fair Market Value per Share calculated as of the day immediately preceding the date the Warrant is presented for exercise, multiplied by such fraction. SECTION 12. Notice to Warrant Holders. Upon any adjustment of the Exercise Price or number or type of securities purchasable upon exercise of the Warrants pursuant to Section 3, the Company shall promptly thereafter (i) cause to be filed with the Company a certificate of the chief financial officer of the Company setting forth the Exercise Price and the number and type of securities or other property constituting Warrant Stock after such adjustment and setting forth in reasonable detail the method of calculation and the facts upon which such calculations are based and, in the case of an adjustment pursuant to Section 3(b), setting forth the number and type of securities or other property constituting Warrant Stock (or portion thereof) issuable, after such adjustment in the Exercise Price or number of Warrant Stock, upon exercise of a Warrant and payment of the adjusted Exercise Price, and (ii) cause to be given to each of the Holders of the Warrant Certificates -12- 14 written notice of such adjustments, together with a copy of such certificate. Where appropriate, such notice may be given in advance and included as a part of the notice required to be given under the other provisions of this Section 11. In the event: (a) the Company shall authorize the payment of any dividend or distribution to holders of shares of Common Stock of capital stock of the Company; or (b) of any capital reorganization, reclassification, recapitalization, consolidation, or share exchange, or sale, lease, conveyance, transfer or other disposition to which the adjustment provisions of Section 3(b) apply, or a purchase, tender or exchange offer for shares of Common Stock or other securities constituting part of the Warrant Stock (whether by the Company or some other party); or (c) of the voluntary or involuntary dissolution, liquidation or winding up of the Company; or (d) the Company proposes to take any action that would require an adjustment of the Exercise Price or number of shares of Warrant Stock for which the Warrants are exercisable; then the Company shall cause to be given to each of the Holders, at least 20 days prior to the applicable record date hereinafter specified (or promptly in the case of events for which there is no record date), a written notice stating (as applicable) (i) the date as of which the holders of record of shares of Common Stock entitled to receive any such dividends or distribution are to be determined, (ii) the date on which any such reclassification, recapitalization or reorganization, consolidation, merger, share exchange, sale, lease, conveyance, transfer or disposition to which the adjustment provisions of Section 3(b) apply or any such dissolution, liquidation or winding up is expected to become effective or be consummated, or (iii) the initial expiration date set forth in any purchase, tender or exchange offer for shares of capital stock, and the date as of which it is expected that holders of record of shares of capital stock or other securities constituting a part of the Warrant Stock (or securities into which the Warrant Stock may be converted) shall be entitled to exchange such shares or securities for securities or other property, if any, deliverable upon such reclassification, recapitalization, reorganization, consolidation, merger, share exchange, sale, lease, conveyance, transfer, disposition, dissolution, liquidation or winding up. SECTION 13. Notices. All notices, consents, approvals, agreements and other communications provided hereunder shall be in writing and delivered personally, by mail, by overnight courier (providing proof of delivery) or by telecopy and shall be sufficiently given to the Purchaser and the Company if addressed or delivered to them at the following addresses: -13- 15 If to Company: Administaff, Inc. 19001 Crescent Springs Drive Kingswood, Texas 77339-3802 Attention: General Counsel Telephone No.: (281) 348-3251 Facsimile No.: (281) 348-2859 with a copy to: Andrews & Kurth L.L.P. 4200 Texas Commerce Tower Houston, Texas 77002 Attention: G. Michael O'Leary Telephone No.: (713) 220-4360 Facsimile No.: (723) 220-4593 If to the Purchaser: American Express Company American Express Tower World Financial Center 200 Vesey Street New York, New York 10285 Attention: General Counsel Telephone No.: (212) 640-5789 Facsimile No.: (212) 267-9061 with a copy to: King & Spalding 191 Peachtree Street Atlanta, Georgia 30303-1763 Attention: John J. Kelley III Telephone No.: (404) 572-3401 Facsimile No.: (404) 572-5146 or at such other address as any party may designate to any other party by written notice. All such notices and communications shall be deemed to have been duly given: (i) at the time delivered by hand, if personally delivered, (ii) when received, if deposited in the mail, postage prepaid, (iii) when transmission is verified, if telecopied, and (iv) on the next Business Day, if timely delivered to an air courier guaranteeing overnight delivery. SECTION 14. Successors. Except as otherwise expressly provided herein or in the Warrants, all covenants and agreements of this Agreement by or on behalf of any of the parties hereto shall bind and inure to the benefit of the respective successors and assigns, including those by operation of law, merger or consolidation. In addition, except as otherwise expressly provided in the Warrants, and whether or not any express assignment has been made, the provisions of this Agreement which are for Purchaser's benefit as a purchaser or Holder of a Warrant or Warrant Stock -14- 16 are also for the benefit of, and enforceable by, any subsequent Holder of such a Warrant or Warrant Stock. SECTION 15. Governing Law. This Agreement, the Warrants and the Warrant Stock shall be governed by those provisions of the General Corporation Law of the State of Delaware and Article 8 of the Delaware Uniform Commercial Code which are necessarily applicable to securities issued by a Delaware corporation and otherwise shall be deemed to be a contract made under the laws of the State of New York and for all purposes shall be construed in accordance with the internal laws of said state. SECTION 16. Benefits of this Agreement. Nothing in this Agreement shall be construed to give to any Person other than the Company and the Holders any legal or equitable right, remedy or claim under this Agreement; this Agreement shall be for the sole and exclusive benefit of the Company and the Holders. SECTION 17. Counterparts. This Agreement may be executed in any number of counterparts and each such counterpart shall for all purposes be deemed to be an original, and all such counterparts shall together constitute one and the same instrument. SECTION 18. Amendment; Waivers. Except as otherwise expressly provided herein, the provisions of this Agreement may be amended or waived and the Company may take any action herein prohibited, or fail to take any action herein required to be performed by it if, but only if, the Company has obtained the written consent of the Holders of a majority of the Warrants in existence at the time such amendment or waiver becomes effective. No failure or delay by any party in exercising any right or remedy hereunder shall operate as a waiver thereof, nor shall a waiver of a particular right or remedy on one occasion be deemed a waiver of any other right or remedy or a waiver of the same right or remedy on any subsequent occasion. SECTION 19. Jurisdiction. Each of the parties hereto hereby agrees that any legal action or proceeding against such party with respect to this Agreement, the Warrants or the Warrant Stock may be brought in the courts of the State of New York or of the United States of America for the Southern District of New York as the other party may elect, and, by execution and delivery hereof, such party accepts and consents for itself and in respect of its property, generally and unconditionally, the jurisdiction of the aforesaid courts and agrees that such jurisdiction shall be exclusive, unless waived by the other party in writing, with respect to any action or proceeding brought by such party against the other party. Each of the parties hereto irrevocably consents to the service of process out of any of the aforementioned courts in any such action or proceeding by the mailing of the copies thereof by certified mail, return receipt requested, postage prepaid, to it at its address set forth herein, such service to become effective upon the earlier of (i) the date ten calendar days after such mailing and (ii) any earlier date permitted by applicable law. -15- 17 SECTION 20. Specific Performance. The Company and the Holders recognize that the rights of the Holder(s) and the Company under this Agreement are unique and, accordingly, the Holder(s) and the Company shall, in addition to such other remedies as may be available to any of them at law or in equity, have the right to enforce their rights hereunder and thereunder by actions for injunctive relief and specific performance to the extent permitted by law. The Company and the Holders agree that monetary damages would not be adequate compensation for any loss incurred by reason of a breach by them of the provisions of this Agreement and the Company and each of the Holders hereby agrees to waive in any action for specific performance the defense that a remedy at law would be adequate. This Agreement is not intended to limit or abridge any rights of the Holder(s) or the Company which may exist apart from this Agreement. SECTION 21. Entire Agreement. The parties hereto agree that this Agreement, the Purchase Agreement, the Confidentiality Agreement and the other Transaction Documents constitute the entire agreement among the parties with respect to the subject matter hereof and supersede all prior agreements and understandings between them as to such subject matter; and there are no restrictions, agreements, arrangements, oral or written, between any or all of the parties relating to the subject matter hereof which are not fully expressed or referred to herein or therein. SECTION 22. Severability. If any provision of this Agreement shall be held or deemed to be, or shall in fact be, invalid, inoperative or unenforceable as applied to any particular case in any jurisdiction or jurisdictions, or in all jurisdictions or in all cases, because of the conflict of any provision with any constitution, statute, rule or public policy, or for any other reason, such circumstances shall not have the effect of rendering the provision or provisions in question, invalid, inoperative or unenforceable in any other jurisdiction or in any other case or circumstance or of rendering any other provision or provisions herein contained invalid, inoperative or unenforceable to the extent that such other provisions are not themselves actually in conflict with such constitution, statute, rule or public policy, but this Agreement shall be reformed and construed in any such jurisdiction or case as if such invalid, inoperative or unenforceable provision had never been contained herein and such provision reformed so that it would be valid, operative and enforceable to the maximum extent permitted in such jurisdiction or in such case. -16- 18 IN WITNESS WHEREOF, the parties hereto have caused this Agreement to be executed by their respective officers thereunto duly authorized as of the day and year first above written. ADMINISTAFF, INC. By: /s/ PAUL J. SARVADI --------------------------------- Name: Paul J. Sarvadi Title: President AMERICAN EXPRESS TRAVEL RELATED SERVICES COMPANY, INC. By: /s/ ANNE BUSQUET --------------------------------- Name: Anne Busquet Title: President, AERS