Document:

<PAGE>

                                    ADVANTAGE(R)
                                PAYROLL SERVICES
   NUMBER                                                              SHARES
------------                                                        ------------
APAY          INCORPORATED UNDER THE LAWS OF THE STATE OF DELAWARE
------------                                                        ------------
COMMON STOCK

                                                              CUSIP 00763Q 10 9
                                             SEE REVERSE FOR CERTAIN DEFINITIONS

This Certifies that

is the owner of

 FULLY PAID AND NONASSESSABLE SHARES OF COMMON STOCK, PAR VALUE $.01 PER SHARE,
                      OF ADVANTAGE PAYROLL SERVICES, INC.

(the "Corporation"), a Delaware corporation. The Shares represented by this
certificate are transferable only on the stock transfer books of the Corporation
by the holder of record hereof, or by his duly authorized attorney or legal
representative, upon the surrender of this certificate properly endorsed. This
certificate is not valid until countersigned and registered by the Corporation's
transfer agent and registrar.

     IN WITNESS WHEREOF, the Corporation has caused this certificate to be
executed by the facsimile signature of its duly authorized officers and has
caused a facsimile of its corporate seal to be hereunto affixed.

                     [Corporate Seal of Advantage Payroll]

Dated:

          /s/ XXXXXXXXXXXXXXXX                  /s/ XXXXXXXXXXXXXXXXXXX
           Vice President and                   Chairman, President and
           Chief Financial Officer              Chief Executive Officer

Countersigned and Registered:
EquiServe Trust Company, N.A.
Transfer Agent and Registrar

BY /s/ XXXXXXXXXXXXXXXXX
Authorized Signature

<PAGE>

                        ADVANTAGE PAYROLL SERVICES, INC.

     The Corporation is authorized to issue multiple classes of stock. The
Corporation will furnish a full statement or summary of the designations,
preferences, conversion and other rights, voting powers, restrictions,
limitations as to dividends, qualifications and terms and conditions of
redemption of each class of stock which the Corporation is authorized to issue
to any stockholder upon request and without charge.

     The following abbreviations, when used in the inscription on the face of
this Certificate, shall be construed as though they were written out in full
according to applicable laws or regulations:

TEN COM - as tenants in common          UNIF GIFT MIN ACT -_____Custodian_______
                                                          (Cust)         (Minor)
                                                   under Uniform Gifts to Minors
TEN ENT - as tenants by the entireties
                                                   Act__________________________
                                                         (State)

JT TEN  - as joint tenants with right
          of survivorship and not as
          tenants in common

    Additional abbreviations may also be used though not in the above list.

     For value received,__________________________ hereby sell, assign and
transfer unto

PLEASE INSERT SOCIAL SECURITY OR OTHER
IDENTIFYING NUMBER OF ASSIGNEE
--------------------------------------

--------------------------------------__________________________________________

_______________________________________________________________________________
  (PLEASE PRINT OR TYPEWRITE NAME AND ADDRESS, INCLUDING ZIP CODE, OF ASSIGNEE)

________________________________________________________________________________

________________________________________________________________________________

________________________________________________________________________ shares

of the capital stock represented by the within Certificate and do hereby
irrevocably constitute and appoint ____________________________________ Attorney
to transfer the said stock on the books of the within named Corporation with
full power of substitution in the premises.

Dated:____________________________

NOTICE:

______________________________________________________________________________
THE SIGNATURE TO THIS ASSIGNMENT MUST CORRESPOND WITH THE NAME AS WRITTEN UPON
THE FACE OF THE CERTIFICATE IN EVERY PARTICULAR, WITHOUT ALTERATION OR
ENLARGEMENT, OR ANY CHANGE WHATSOEVER.

Signature(s) Guaranteed:

______________________________________________________________________________
THE SIGNATURE(S) SHOULD BE GUARANTEED BY AN ELIGIBLE GUARANTOR INSTITUTION
(BANKS, STOCKBROKERS, SAVINGS AND LOAN ASSOCIATIONS AND CREDIT UNIONS WITH
MEMBERSHIP IN AN APPROVED SIGNATURE GUARANTEE MEDALLION PROGRAM), PURSUANT TO
S.E.C. RULE 17Ad-15.

BANKNOTE CORP. OF AMERICA . BROWNS SUMMIT (NC) . ADVANTAGE PAYROLL SERVICES,
INC. . 1-204035-942 . PROOF #1 . 9:54 AM . 4/23/02 . SMS .<PAGE>

                                                                     Exhibit 4.2

                                                                  Execution Copy

                   ADVANTAGE BUSINESS SERVICES HOLDINGS, INC.
                   ------------------------------------------

                         REGISTRATION RIGHTS AGREEMENT
                         -----------------------------

          THIS REGISTRATION RIGHTS AGREEMENT (the "Agreement") is made as of
                                                   ---------
February 10, 1998 by and among Advantage Business Services Holdings, Inc., a
Delaware corporation (the "Company"), the Persons listed on the signature pages
                           -------
hereto as "Investors" (the "Investors") and the Persons listed on the signature
                            ---------
pages hereto as "Other Stockholders" (the "Other Stockholders"). The Company,
                                           ------------------
the Investors, the Other Stockholders are sometimes collectively referred to
herein as "Parties" and individually as a "Party."
           -------                         -----

          The parties to this Agreement are parties to a Purchase and
Recapitalization Agreement of even date herewith (the "Recapitalization
                                                       ----------------
Agreement"). In order to induce the Investors to enter into the Recapitalization
---------
Agreement, the Company has agreed to provide the registration rights set forth
in this Agreement. The execution and delivery of this Agreement is a condition
to the execution and closing under the Recapitalization Agreement. Unless
otherwise provided in this Agreement, capitalized terms used herein shall have
the meanings set forth in Section 8 hereof.
                          ---------

          The parties hereto agree as follows:

          1. Demand Registrations
             --------------------

          (a) Requests for Registration. At any time, the holders of at least
              -------------------------
50% of the Investor Registrable Securities may request registration under the
Securities Act of all or any portion of their Investor Registrable Securities on
Form S-1, S-2 or S-3 or any other similar form ("Demand Registrations"). Each
                                                 --------------------
request for a Demand Registration shall specify the approximate number of
Investor Registrable Securities requested to be registered and the anticipated
per share price range for such offering. Within ten days after receipt of any
such request, the Company shall give written notice of such requested
registration to all other holders of Investor Registrable Securities and shall
include in such registration all Investor Registrable Securities with respect to
which the Company has received written requests for inclusion therein within 15
days after the receipt of the Company's notice.

          (b) Number of Demand Registrations. The holders of Investor
              ------------------------------
Registrable Securities shall be entitled to request any number of Demand
Registrations and, in each such Demand Registration, the Company shall pay all
Registration Expenses (as defined in Section 5 hereof).
                                     ---------

          (c) Priority on Demand Registrations. The Company shall not include in
              --------------------------------
any Demand Registration any securities which are not Investor Registrable
Securities without the prior written consent of the holders of at least 50% of
the Investor Registrable Securities initially requesting such registration. If a
Demand Registration is an underwritten offering and the managing

<PAGE>

underwriters advise the Company in writing that in their opinion the number of
Investor Registrable Securities and, if permitted hereunder, other securities
requested to be included in such offering exceeds the number of Investor
Registrable Securities and other securities, if any, which can be sold in an
orderly manner in such offering within a price range acceptable to the holders
of a majority of the Investor Registrable Securities initially requesting
registration, the Company shall include in such registration, prior to the
inclusion of any securities which are not Investor Registrable Securities, the
number of Investor Registrable Securities requested to be included which in the
opinion of such underwriters can be sold in an orderly manner within the price
range of such offering, pro rata among the respective holders thereof on the
basis of the amount of Investor Registrable Securities owned by each such
holder.

          (d) Selection of Underwriters. The holders of a majority of the
              -------------------------
Investor Registrable Securities initially requesting registration hereunder
shall have the right to select the investment banker(s) and manager(s) to
administer the offering.

          (e) Other Registration Rights. Except as provided in this Agreement,
              -------------------------
the Company shall not grant to any Persons the right to request the Company to
register any equity securities of the Company, or any securities convertible or
exchangeable into or exercisable for such securities, without the prior written
consent of the holders of at least 50% of the Investor Registrable Securities.

          2. Piggyback Registrations.
             -----------------------

          (a) Right to Piggyback. Whenever the Company proposes to register any
              ------------------
of its securities under the Securities Act and the registration form to be used
may be used for the registration of Registrable Securities (a "Piggyback
                                                               ---------
Registration"), the Company shall give prompt written notice to all holders of
------------
Registrable Securities of its intention to effect such a registration and shall
include in such registration all Registrable Securities with respect to which
the Company has received written requests for inclusion therein within 20 days
after the receipt of the Company's notice.

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

          (c) Priority on Primary Registrations. If a Piggyback Registration is
              ---------------------------------
an underwritten primary registration on behalf of the Company, and the managing
underwriters advise the Company in writing that in their opinion the number of
securities requested to be included in such registration exceeds the number
which can be sold in such offering without adversely affecting the marketability
of the offering, the Company shall include in such registration (i) first, the
securities the Company proposes to sell, (ii) second, the Investor Registrable
Securities requested to be included in such registration, pro rata among the
holders of such Investor Registrable Securities on the basis of the number of
shares owned by each such holder, (iii) the Other Stockholder Registrable
Securities requested to be included in such registration, pro rata among the
holders of such Other Stockholder

                                       -2-

<PAGE>

Registrable Securities on the basis of the number of shares owned by each such
holder, and (iv) fourth, other securities requested to be included in such
registration; provided that in any event the holders of the Investor Registrable
              --------
Securities shall be entitled to register at least 50% of the securities to be
included in any such registration.

          (d) Priority on Secondary Registrations. If a Piggyback Registration
              -----------------------------------
is an underwritten secondary registration on behalf of holders of the Company's
securities, and the managing underwriters advise the Company in writing that in
their opinion the number of securities requested to be included in such
registration exceeds the number which can be sold in an orderly manner in such
offering within a price range acceptable to the holders initially requesting
such registration, the Company shall include in such registration (i) first, the
securities requested to be included therein by the holders requesting such
registration and the Investor Registrable Securities requested to be included in
such registration, pro rata among the holders of such securities on the basis of
the number of securities so requested to be included therein owned by each such
holder, (ii) second, the Other Stockholder Registrable Securities requested to
be included therein, pro rata among the holders of such securities on the basis
of the number of securities so requested to be included therein owned by each
such holder, and (iii) third, other securities requested to be included in such
registration.

          (e) Selection of Underwriters. If any Piggyback Registration is an
              -------------------------
underwritten offering, the selection of investment banker(s) and manager(s) for
the offering must be approved by the holders of a majority of the Investor
Registrable Securities included in such Piggyback Registration. Such approval
shall not be unreasonably withheld.

          (f) Other Registrations. If the Company has previously filed a
              -------------------
registration statement with respect to Registrable Securities pursuant to
Section 1 or pursuant to this Section 2, and if such previous registration has
---------                     ---------
not been withdrawn or abandoned, the Company shall not file or cause to be
effected any other registration of any of its equity securities or securities
convertible or exchangeable into or exercisable for its equity securities under
the Securities Act (except on Form S-8 or any successor form), whether on its
own behalf or at the request of any holder or holders of such securities, until
a period of at least 90 days has elapsed from the effective date of such
previous registration.

          3. Holdback Agreements.
             -------------------

          (a) No holder of Registrable Securities shall effect any public sale
or distribution including sales pursuant to Rule 144) of equity securities of
the Company, or any securities convertible into or exchangeable or exercisable
for such securities, during the seven days prior to, and the 180-day period
beginning on, the effective date of any underwritten Demand Registration or any
underwritten Piggyback Registration in which Registrable Securities are included
(except as part of such underwritten registration), unless the underwriters
managing the registered public offering otherwise agree.

                                       -3-

<PAGE>

          (b) The Company (i) shall not effect any public sale or distribution
of its equity securities, or any securities convertible into or exchangeable or
exercisable for such securities, during the seven days prior to, and during the
180-day period beginning on, the effective date of any underwritten Demand
Registration or any underwritten Piggyback Registration (except as part of such
underwritten registration or pursuant to registrations on Form S-8 or any
successor form), unless the underwriters managing the registered public offering
otherwise agree, and (ii) shall cause each holder of at least 2% (on a
fully-diluted basis) of its Common Stock, or any 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 (including
sales pursuant to Rule 144) of any such securities during such period (except as
part of such underwritten registration, if otherwise permitted), unless the
underwriters managing the registered public offering otherwise agree.

          4. Registration Procedures. Whenever the holders of Registrable
             -----------------------
Securities have requested that any Registrable Securities be registered pursuant
to this Agreement, the Company shall use its reasonable best efforts to effect
the registration and the sale of such Registrable Securities in accordance with
the intended method of disposition thereof, and pursuant thereto the Company
shall as expeditiously as possible:

          (a) prepare and file with the Securities and Exchange Commission a
registration statement with respect to such Registrable Securities and use its
reasonable best efforts to cause such registration statement to become effective
(provided that before filing a registration statement or prospectus or any
amendments or supplements thereto, the Company shall furnish to the counsel
selected by the holders of a majority of the Registrable Securities covered by
such registration statement copies of all such documents proposed to be filed,
which documents shall be subject to the review and comment of such counsel);

          (b) notify each holder of Registrable Securities of the effectiveness
of each registration statement filed hereunder and prepare and file with the
Securities and Exchange Commission such amendments and supplements to such
registration statement and the prospectus used in connection therewith as may be
necessary to keep such registration statement effective for a period of not less
than 180 days and comply with the provisions of the Securities Act with respect
to the disposition of all securities covered by such registration statement
during such period in accordance with the intended methods of disposition by the
sellers thereof set forth in such registration statement;

          (c) furnish to each seller of Registrable Securities such number of
copies of such registration statement, each amendment and supplement thereto,
the prospectus included in such registration statement (including each
preliminary prospectus) and such other documents as such seller may reasonably
request in order to facilitate the disposition of the Registrable Securities
owned by such seller;

                                       -4-

<PAGE>

          (d) use its reasonable best efforts to register or qualify such
Registrable Securities under such other securities or blue sky laws of such
jurisdictions as any seller reasonably requests and do any and all other acts
and things which may be reasonably necessary or advisable to enable such seller
to consummate the disposition in such jurisdictions of the Registrable
Securities owned by such seller (provided that the Company shall not be required
to (i) qualify generally to do business in any jurisdiction where it would not
otherwise be required to qualify but for this subparagraph, (ii) subject itself
to taxation in any such jurisdiction or (iii) consent to general service of
process in any such jurisdiction);

          (e) notify each seller of such Registrable Securities, at any time
when a prospectus relating thereto is required to be delivered under the
Securities Act, of the happening of any event as a result of which the
prospectus included in such registration statement contains an untrue statement
of a material fact or omits any fact necessary to make the statements therein
not misleading, and, at the request of any such seller, the Company shall
prepare a supplement or amendment to such prospectus so that, as thereafter
delivered to the purchasers of such Registrable Securities, such prospectus
shall not contain an untrue statement of a material fact or omit to state any
fact necessary to make the statements therein not misleading;

          (f) cause all such Registrable Securities to be listed on each
securities exchange on which similar securities issued by the Company are then
listed and, if not so listed, to be listed on the National Association of
Securities Dealers ("NASD") automated quotation system and, if listed on the
                     ----
NASD automated quotation system ("NASDAQ"), use its best efforts to secure
                                  ------
designation of all such Registrable Securities covered by such registration
statement as a NASDAQ "national market system security" within the meaning of
Rule 11Aa2-1 of the Securities and Exchange Commission or, failing that, to
secure NASDAQ authorization for such Registrable Securities and, without
limiting the generality of the foregoing, to arrange for at least two market
makers to register as such with respect to such Registrable Securities with the
NASD;

          (g) provide a transfer agent and registrar for all such Registrable
Securities not later than the effective date of such registration statement;

          (h) enter into such customary agreements (including underwriting
agreements in customary form) and take all such other actions as the holders of
a majority of the Registrable Securities being sold or the underwriters, if any,
reasonably request in order to expedite or facilitate the disposition of such
Registrable Securities (including effecting a stock split or a combination of
shares);

          (i) make available for inspection by any seller of Registrable
Securities, any underwriter participating in any disposition pursuant to such
registration statement and any attorney, accountant or other agent retained by
any such seller or underwriter, all financial and other records, pertinent
corporate documents and properties of the Company, and cause the Company's
officers, directors, employees and independent accountants to supply all
information reasonably requested by

                                       -5-

<PAGE>

any such seller, underwriter, attorney, accountant or agent in connection with
such registration statement;

          (j) otherwise use its best efforts to comply with all applicable rules
and regulations of the Securities and Exchange Commission, and make available to
its security holders, as soon as reasonably practicable, an earnings statement
covering the period of at least twelve months beginning with the first day of
the Company's first full calendar quarter after the effective date of the
registration statement, which earnings statement shall satisfy the provisions of
Section 11(a) of the Securities Act and Rule 158 thereunder;

          (k) permit any holder of Registrable Securities which holder, in its
sole and exclusive judgment, might be deemed to be an underwriter or a
controlling person of the Company, to participate in the preparation of such
registration or comparable statement and to require the insertion therein of
material, furnished to the Company in writing, which in the reasonable judgment
of such holder and its counsel should be included;

          (1) in the event of the issuance of any stop order suspending the
effectiveness of a registration statement, or of any order suspending or
preventing the use of any related prospectus or suspending the qualification of
any common stock included in such registration statement for sale in any
jurisdiction, the Company shall use its best efforts promptly to obtain the
withdrawal of such order;

          (m) use its best efforts to cause such Registrable Securities covered
by such registration statement to be registered with or approved by such other
governmental agencies or authorities as may be necessary to enable the sellers
thereof to consummate the disposition of such Registrable Securities; and

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

          5. Registration Expenses
             ---------------------

          (a) All expenses incident to the Company's performance of or
compliance with this Agreement, including, without limitation, all registration
and filing fees, fees and expenses of compliance with securities or blue sky
laws, printing expenses, messenger and delivery expenses, fees and disbursements
of custodians, and fees and disbursements of counsel for the Company and all
independent certified public accountants, underwriters (excluding discounts and
commissions) and other Persons retained by the Company (all such expenses being
herein called "Registration Expenses"), shall be borne as provided in this
               --------------------
Agreement, except that the Company shall, in any event, pay its internal
expenses (including, without limitation, all salaries and expenses of its
officers and employees performing legal or accounting duties), the expense of
any annual audit or quarterly review, the expense of any liability insurance and
the expenses and fees for listing the securities to be

                                       -6-

<PAGE>

registered on each securities exchange on which similar securities issued by the
Company are then listed or on the NASDAQ.

          (b) In connection with each Demand Registration and each Piggyback
Registration, the Company shall reimburse the holders of Registrable Securities
included in such registration for the reasonable fees and disbursements of one
counsel chosen by the holders of a majority of the Investor Registrable
Securities initially requesting such registration.

          (c) To the extent Registration Expenses are not required to be paid by
the Company, each holder of securities included in any registration hereunder
shall pay those Registration Expenses allocable to the registration of such
holder's securities so included, and any Registration Expenses not so allocable
shall be borne by all sellers of securities included in such registration in
proportion to the aggregate selling price of the securities to be so registered.

          6. Indemnification.
             ---------------

          (a) The Company agrees to indemnify, to the extent permitted by law,
each holder of Registrable Securities, its officers and directors and each
Person who controls such holder (within the meaning of the Securities Act)
against all losses, claims, damages, liabilities and expenses caused by any
untrue or alleged untrue statement of material fact contained in any
registration statement, prospectus or preliminary prospectus or any amendment
thereof or supplement thereto or any omission or alleged omission of a material
fact required to be stated therein or necessary to make the statements therein
not misleading, except insofar as the same are caused by or contained in any
information furnished in writing to the Company by such holder expressly for use
therein or by such holder's failure to deliver a copy of the registration
statement or prospectus or any amendments or supplements thereto after the
Company has furnished such holder with a sufficient number of copies of the
same. In connection with an underwritten offering, the Company shall indemnify
such underwriters, their officers and directors and each Person who controls
such underwriters (within the meaning of the Securities Act) to the same extent
as provided above with respect to the indemnification of the holders of
Registrable Securities.

          (b) In connection with any registration statement in which a holder of
Registrable Securities is participating, each such holder shall furnish to the
Company in writing such information and affidavits as the Company reasonably
requests for use in connection with any such registration statement or
prospectus and, to the extent permitted by law, shall indemnify the Company, its
directors and officers and each Person who controls the Company (within the
meaning of the Securities Act) against any losses, claims, damages, liabilities
and expenses resulting from any untrue or alleged untrue statement of material
fact contained in the registration statement, prospectus or preliminary
prospectus or any amendment thereof or supplement thereto or any omission or
alleged omission of a material fact required to be stated therein or necessary
to make the statements therein not misleading, but only to the extent that such
untrue statement or omission is contained in any information or affidavit so
furnished in writing by such holder; provided that the obligation to indemnify
shall be individual, not joint and several, for each holder and shall be limited
to the net

                                       -7-

<PAGE>

amount of proceeds received by such holder from the sale of Registrable
Securities pursuant to such registration statement.

          (c) Any Person entitled to indemnification hereunder shall (i) give
prompt written notice to the indemnifying party of any claim with respect to
which it seeks indemnification (provided that the failure to give prompt notice
shall not impair any Person's right to indemnification hereunder to the extent
such failure has not prejudiced the indemnifying party) and (ii) unless in such
indemnified party's reasonable judgment a conflict of interest between such
indemnified and indemnifying parties may exist with respect to such claim,
permit such indemnifying party to assume the defense of such claim with counsel
reasonably satisfactory to the indemnified party. If such defense is assumed,
the indemnifying party shall not be subject to any liability for any settlement
made by the indemnified party without its consent (but such consent shall not be
unreasonably withheld). An indemnifying party who is not entitled to, or elects
not to, assume the defense of a claim shall not be obligated to pay the fees and
expenses of more than one counsel for all parties indemnified by such
indemnifying party with respect to such claim, unless in the reasonable judgment
of any indemnified party a conflict of interest may exist between such
indemnified party and any other of such indemnified parties with respect to such
claim.

          (d) The indemnification provided for under this Agreement shall remain
in full force and effect regardless of any investigation made by or on behalf of
the indemnified party or any officer, director or controlling Person of such
indemnified party and shall survive the transfer of securities. The Company also
agrees to make such provisions, as are reasonably requested by any indemnified
party, for contribution to such party in the event the Company's indemnification
is unavailable for any reason.

          7. Participation in Underwritten Registrations. No Person may
             -------------------------------------------
participate in any registration hereunder which is underwritten unless such
Person (a) agrees to sell such Person's securities on the basis provided in any
underwriting arrangements approved by the Person or Persons entitled hereunder
to approve such arrangements and (b) completes and executes all questionnaires,
powers of attorney, indemnities, underwriting agreements and other documents
required under the terms of such underwriting arrangements; provided that no
holder of Registrable Securities included in any underwritten registration shall
be required to make any representations or warranties to the Company or the
underwriters (other than representations and warranties regarding such holder
and such holder's intended method of distribution) or to undertake any
indemnification obligations to the Company or the underwriters with respect
thereto, except as otherwise provided in paragraph 6 hereof.

          8. Definitions.
             -----------

          (a) "Investor Registrable Securities" means (i) any Common Stock
               -------------------------------
issued to the Investors pursuant to the Recapitalization Agreement, (ii) any
Common Stock referred to in clause (i) that have been purchased, acquired or
otherwise transferred from the Investors to any other Person, (iii) any Common
Stock issued or issuable with respect to the equity securities referred to

                                       -8-

<PAGE>

in clauses (i) and (ii) above by way of a stock dividend or stock split or in
connection with a combination of shares, recapitalization, merger, consolidation
or other reorganization and (iv) any other Common Stock held by Persons holding
the equity securities described in clauses (i) through (iii) inclusive, above.

          (b) "Other Stockholder Registrable Securities" means any Common Stock
               ----------------------------------------
held as of the date hereof, or acquired hereafter, by stockholders (other than
the Investors) or employees of the Company and its Subsidiaries who are or
become parties to this Agreement.

          (c) "Registrable Securities" means Investor Registrable Securities and
               ----------------------
Other Stockholder Registrable Securities. As to any particular Registrable
Securities, such securities shall cease to be Investor or Other Stockholder
Registrable Securities when they have been distributed to the public pursuant to
a offering registered under the Securities Act or sold to the public through a
broker, dealer or market maker in compliance with Rule 144 under the Securities
Act (or any similar rule then in force). For purposes of this Agreement, a
Person shall be deemed to be a holder of Registrable Securities whenever such
Person has the right to acquire such Registrable Securities (upon conversion or
exercise in connection with a transfer of securities or otherwise, but
disregarding any restrictions or limitations upon the exercise of such right),
whether or not such acquisition has actually been effected.

          (d) Unless otherwise stated, other capitalized terms contained herein
have the meanings set forth in the Recapitalization Agreement.

          9. Miscellaneous
             -------------

          (a) Selection of Investment Bankers. Except as otherwise provided
              -------------------------------
herein in connection with Demand Registrations, the selection of investment
banker(s) and manager(s) for any public offering or private sale by the Company
of its securities must be approved by the holders of a majority of the Investor
Registrable Securities initially requesting such registration, which approval
shall not be unreasonably withheld.

          (b) No Inconsistent Agreements. The Company shall not hereafter enter
              --------------------------
into any agreement with respect to its securities which is inconsistent with or
violates the rights granted to the holders of Registrable Securities in this
Agreement.

          (c) Adjustments Affecting Registrable Securities. The Company
              --------------------------------------------
shall not take any action, or permit any change to occur, with respect to its
securities which would adversely affect the ability of the holders of Investor
Registrable Securities to include such Investor Registrable Securities in a
registration undertaken pursuant to this Agreement or which would adversely
affect the marketability of such Investor Registrable Securities in any such
registration (including, without limitation, effecting a stock split or a
combination of shares).

                                       -9-

<PAGE>

          (d) Remedies. Any Person having rights under any provision of this
              --------
Agreement shall be entitled to enforce such rights specifically to recover
damages caused by reason of any breach of any provision of this Agreement and to
exercise all other rights granted by law. The parties hereto agree and
acknowledge that money damages may not be an adequate remedy for any breach of
the provisions of this Agreement and that any party may in its sole discretion
apply to any court of law or equity of competent jurisdiction (without posting
any bond or other security) for specific performance and for other injunctive
relief in order to enforce or prevent violation of the provisions of this
Agreement.

          (e) Amendment and Waivers. Except as otherwise provided herein, the
              ---------------------
provisions of this Agreement may be amended or waived only upon the prior
written consent of the Company and holders of at least 50% of the Investor
Registrable Securities and at least 50% of the Registrable Securities.

          (f) Successors and Assigns. All covenants and agreements in this
              ----------------------
Agreement by or on behalf of any of the parties hereto shall bind and inure to
the benefit of the respective successors and assigns of the parties hereto
whether so expressed or not. In addition, whether or not any express assignment
has been made, the provisions of this Agreement which are for the benefit of
purchasers or holders of Registrable Securities are also for the benefit of, and
enforceable by, any subsequent holder of Registrable Securities.

          (g) Severability. Whenever possible, each provision of this Agreement
              ------------
shall be interpreted in such manner as to be effective and valid under
applicable law, but if any provision of this Agreement is held to be prohibited
by or invalid under applicable law, such provision shall be ineffective only to
the extent of such prohibition or invalidity, without invalidating the remainder
of this Agreement.

          (h) Counterparts. This Agreement may be executed simultaneously in
              ------------
counterparts, any one of which need not contain the signatures of more than one
party, but all such counterparts taken together shall constitute one and the
same Agreement.

          (i) Descriptive Headings: Interpretation. The descriptive headings of
              ------------------------------------
this Agreement are inserted for convenience only and do not constitute a
substantive part of this Agreement. The use of the word "including" in this
Agreement shall be by way of example rather than by limitation.

          (j) Governing Law. All issues and questions concerning the
              -------------
construction, validity, enforcement and interpretation of this Agreement and the
exhibits and schedules hereto shall be governed by, and construed in accordance
with, the laws of the State of Delaware, without giving effect to any choice of
law or conflict of law rules or provisions (whether of the State of Delaware or
any other jurisdiction) that would cause the application of the laws of any
jurisdiction other than the State of Delaware.

                                      -10-

<PAGE>

          (k) Notices. All notices, demands or other communications to be given
              -------
or delivered under or by reason of the provisions of this Agreement shall be
in writing and shall be deemed to have been given when delivered personally to
the recipient, one day after being sent to the recipient by reputable overnight
courier service (charges prepaid) or five days after being mailed to the
recipient by certified or registered mail, return receipt requested and postage
prepaid. Such notices, demands and other communications shall be sent to the
Company, the Investors and the Other Stockholders at the addresses indicated on
the Notices Schedule attached hereto or to such other address or to the
    ----------------
attention of such other person as the recipient party has specified by prior
written notice to the sending party.

          (l) No Strict Construction. The parties hereto have participated
              ----------------------
jointly in the negotiation and drafting of this Agreement. In the event an
ambiguity or question of intent or interpretation arises, this Agreement shall
be construed as if drafted jointly by the parties hereto, and no presumption or
burden of proof shall arise favoring or disfavoring any party by virtue of the
authorship of any of the provisions of this Agreement.

                                   * * * * *

                                      -11-

<PAGE>

     IN WITNESS WHEREOF, the parties have executed this Registration Rights
     Agreement on the date first written above.

                                      ADVANTAGE BUSINESS SERVICES HOLDINGS, INC.

                                      By: /s/ CHARLES W. LATHROP, JR
                                          --------------------------------------
                                      Its: President
                                           -------------------------------------

                                      INVESTORS

                                      WILLIS STEIN & PARTNERS, L.P.

                                      By: Willis Stein & Partners, L.L.C.
                                      Its: General Partner

                                      By: /s/ Daniel Gill
                                          --------------------------------------
                                      Its: Managing Director
                                          --------------------------------------

                                      OTHER STOCKHOLDERS

                                      /s/ CHARLES W. LATHROP, JR
                                      ------------------------------------------
                                      CHARLES W. LATHROP,JR

                                      /s/ NANCY M. FRENCH
                                      ------------------------------------------
                                      NANCY M. FRENCH

                                      /s/ W. SCOTT ADAIR
                                      ------------------------------------------
                                      W. SCOTT ADAIR

                                      /s/ THOMAS G. POLING
                                      ------------------------------------------
                                      THOMAS G. POLING

<PAGE>

                   AMENDMENT TO REGISTRATION RIGHTS AGREEMENT
                   ------------------------------------------

     THIS AMENDMENT TO REGISTRATION RIGHTS AGREEMENT (this "Amendment") entered
                                                            ---------
into as of March 23, 2000 by and between ADVANTAGE BUSINESS SERVICES HOLDINGS,
INC., a Delaware corporation located at 126 Merrow Road, P.O. Box 1330, Auburn,
Maine 04211-1330 (the "Company"); the Persons listed on the signature pages
                       -------
hereto as "Investors", the Persons listed on the signature pages hereto as
"Other Stockholders" and NEW ENGLAND BUSINESS SERVICE, INC., a Delaware
corporation located at 500 Main Street, Groton, Massachusetts 01471 ("NEBS").
                                                                      ----

                                    RECITALS
                                    --------

     WHEREAS, the Company and certain of its Shareholders have entered into a
Registration Rights Agreement, dated as of February 10, 1998 (the "Agreement");
                                                                   ---------
which Agreement provides the parties thereto other than the Company with certain
rights to have the Company register shares of the Company's stock held by such
parties and provides further that the Company may not grant to any person
registration rights except as provided therein without the written consent of at
least 50% of the Investor Registrable Securities and that any registration
rights granted may not be inconsistent with the rights granted holders of
Registrable Securities under the Agreement; and

     WHEREAS, the Company, subsequently entered into a Registration Rights
Agreement dated as of July 23, 1999 with certain additional shareholders (the
"Second Agreement"), which Second Agreement provides such Shareholders with
 ----------------
certain rights to have the Company register shares of the Company's stock held
by them and provides further that the Company shall not thereafter enter into
any agreement which is inconsistent with the Second Agreement; and

     WHEREAS, the Company and NEBS have this day consummated a Purchase and Sale
Agreement dated as of March 23, 2000, pursuant to which NEBS has been issued
Common Stock of the Company together with Warrants to purchase additional Common
Stock of the Company (such presently issued shares, together with any shares to
be issued pursuant to the Warrants, being hereinafter collectively referred to
as the "NEBS Shares"); and
        -----------

     WHEREAS, the Company wishes to provide NEBS, with the same registration
rights with respect to the NEBS Shares provided to Other Stockholders (other
than the Investors) by the Registration Rights Agreement to the extent not
inconsistent with the Second Agreement.

     NOW, THEREFORE, in consideration of the premises and the mutual promises
herein made and the recitals stated above which are incorporated into this
Amendment, and in consideration of the representations, warranties, covenants,
agreements and understandings herein contained, the Parties agree as follows:

     1. Terms not otherwise defined in this Amendment shall have the meanings
set forth in the Agreement.

<PAGE>

     2. NEBS hereby becomes a party to the Agreement which is incorporated into
this Amendment by reference, and agrees to be bound by all the terms and
conditions thereof, and shall have the same rights and responsibilities
thereunder as a holder of Other Stockholder Registrable Securities and shall be
one of the "Other Stockholders" for purposes of the Agreement. Each reference in
the Agreement to "Other Stockholder Registrable Securities", or any related or
derivative term, shall be deemed to include the NEBS Shares, except as the
context may otherwise require.

     3. The Agreement shall be amended to provide that no subsequent amendment
thereto which adversely and disproportionately affects the rights of NEBS
thereunder shall be effective as to NEBS without NEBS' written consent, provided
that (i) a grant of registration rights which are pari passu with the
registration rights of NEBS and an amendment to the Agreement to add thereto as
parties the person or persons to whom such registration rights are granted and
(ii) a grant of registration rights which are superior to, or pari passu with,
the registration rights of the holders of the Investor Registrable Securities
with the written consent of the holders of at least 50% of the Investor
Registrable Securities and an amendment to the Agreement to add thereto as
parties the person or persons to whom such registration rights are granted shall
not be deemed to affect NEBS adversely.

     4. Notwithstanding anything herein to be contrary, to the extent that any
provision of this Amendment or any of the rights granted to NEBS hereunder are
inconsistent with, or violates any provision of, the Second Agreement, then the
Second Agreement shall control and each such provision or right of NEBS shall be
interpreted to the fullest extent possible without creating such inconsistency
or violation.

     5. The "Registration Rights Agreement Notices Schedule" attached at the end
of the, Agreement shall be amended by the addition thereto of the following:

                    New England Business Service, Inc.,
                    500 Main Street,
                    Groton, MA 01471
                    Attention: General Counsel

     6. This Amendment shall be effective when executed by persons holding at
least 50% of the Investor Registrable Securities and at least 50% of the
Registrable Securities, determined immediately prior to the effectiveness of
this Amendment. By signing this Amendment, the holders of Investor Registrable
Securities and Registrable Securities consent to the grant of registration
rights provided for herein and to this Amendment. This Amendment may be executed
in counterparts, any one of which need not contain the signatures of more than
one party, but all such counterparts shall constitute one and the same
agreement.

     7. It is expressly understood and agreed that if, at any time or under any
circumstances, any provision of this Amendment or its effect shall be deemed
invalid or unenforceable for any reason, then any or all of such invalid or
unenforceable provisions shall be amended, without any

                                        2

<PAGE>

additional writing or agreement, so as to cause such provision or its effect to
be valid and enforced to the fullest extent permitted.

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

                                       ADVANTAGE BUSINESS SERVICES
                                       HOLDINGS, INC.

                                       By: /s/ Charles W. Lathrop, Jr.
                                           -------------------------------------
                                           Charles W. Lathrop, Jr.
                                           President and Chief Executive Officer

                                       NEW ENGLAND BUSINESS SERVICE. INC.

                                       By: /s/ George P. Allman
                                           -------------------------------------
                                           George P. Allman
                                           Senior Vice President

                                           INVESTORS

                                       WILLIS STEIN & PARTNERS, L.P.

                                       By: Willis Stein & Partners, L.L.C.
                                           Its: General Partner

                                       By: /s/ Daniel Gill
                                           -------------------------------------
                                           Its: Managing Director

                                       OTHER STOCKHOLDERS

                                       /s/ Charles W. Lathrop, Jr.
                                       -----------------------------------------
                                       Charles W. Lathrop, Jr.

                                       /s/ Nancy M. French
                                       -----------------------------------------
                                       Nancy M. French

                                       /s/ Thomas G. Poling
                                       -----------------------------------------
                                       Thomas G. Poling

                                       /s/ W. Scott Adair
                                       -----------------------------------------
                                       W. Scott Adair

                                        3

<PAGE>

                   AMENDMENT TO REGISTRATION RIGHTS AGREEMENT
                   ------------------------------------------

     THIS AMENDMENT TO REGISTRATION RIGHTS AGREEMENT (this "Amendment") entered
                                                            ---------
into as of September 21, 2000 by and between ADVANTAGE BUSINESS SERVICES
HOLDINGS, INC., a Delaware corporation located at 126 Merrow Road, P.O. Box
1330, Auburn, Maine 04211-1330 (the "Company"), the Person listed on the
                                     -------
signature pages hereto as "Investor", and Chris Kapolas, James Kapolas, Mary
Kapolas, Peter J. Pappas, Sr., Suzanne E. Regas, Dean J. Regas and Allyson Regas
(collectively, "Sellers")
                -------

                                    RECITALS
                                    --------

     WHEREAS, the Company and certain of its Shareholders have entered into a
Registration Rights Agreement, dated as of February 10, 1998 (the "Agreement");
                                                                   ---------
which Agreement provides the parties thereto other than the Company with certain
rights to have the Company register shares of the Company's stock held by such
parties and provides further that the Company may not grant to any person
registration rights except as provided therein without the written consent of
the holders of at least 50% of the Investor Registrable Securities and that any
registration rights granted may not be inconsistent with the rights granted
holders of Registrable Securities under the Agreement; and

     WHEREAS, the Company, subsequently entered into a Registration Rights
Agreement dated as of July 23, 1999 with certain additional shareholders (the
"Second Agreement"), which Second Agreement provides such Shareholders with
 ----------------
certain rights to have the Company register shares of the Company's stock held
by them and provides further that the Company shall not thereafter enter into
any agreement which is inconsistent with the Second Agreement; and

     WHEREAS, the Company and certain of its shareholders entered into an
Amendment to Registration Rights Agreement dated as of March 23, 2000 (the
"Third Agreement") in connection with the issuance to New England Business
 ---------------
Service, Inc. ("NEBS") of Common Stock of the Company together with Warrants to
                ----
purchase additional Common Stock of the Company which Third Agreement provides
that the Agreement, as amended, may be further amended to provide registration
rights which are pari passu with the registration rights of NEBS, and

     WHEREAS, the Company and Sellers have this day consummated an Agreement and
Plan of Merger dated as of September 21, 2000 pursuant to which Sellers have
been issued Common Stock of the Company (the "Sellers' Shares") in connection
                                              ---------------
with the merger of Related Payroll Services, Inc. with and into a subsidiary of
the Company; and

     WHEREAS, the Company wishes to provide Sellers, with the same registration
rights with respect to the Sellers' Shares as have been provided to NEBS and
Other Stockholders (other than the Investors) by the Agreement, as amended, to
the extent not inconsistent with the Second Agreement and Third Agreement.

<PAGE>

     NOW, THEREFORE, in consideration of the premises and the mutual promises
herein made and the recitals stated above which are incorporated into this
Amendment, and in consideration of the representations, warranties, covenants,
agreements and understandings herein contained, the Parties agree as follows:

     1. Terms not otherwise defined in this Amendment shall have the meanings
set forth in the Agreement.

     2. Each of the Sellers hereby becomes a party to the Agreement which is
incorporated into this Amendment by reference, and agrees to be bound by all the
terms and conditions thereof, and shall have the same rights and
responsibilities thereunder as a holder of Other Stockholder Registrable
Securities and shall be one of the "Other Stockholders" for purposes of the
Agreement. Each reference in the Agreement to "Other Stockholder Registrable
Securities", or any related or derivative term, shall be deemed to include the
Sellers' Shares, except as the context may otherwise require.

     3. Notwithstanding anything herein to be contrary, to the extent that any
provision of this Amendment or any of the rights granted to the Sellers
hereunder are inconsistent with, or violates any provision of, the Second
Agreement, then the Second Agreement shall control and each such provision or
right of the Sellers shall be interpreted to the fullest extent possible without
creating such inconsistency or violation.

     4. The "Registration Rights Agreement Notices Schedule" attached at the end
of the Agreement shall be amended by the addition thereto of the following:

                     If to Chris Kapolas, James Kapolas or Mary Kapolas, to:
                     c/o James Kapolas
                     126 Forest Trail
                     Oak Brook, IL 60521

                     If to Suzanne E. Regas, Dean J. Regas or Allyson Regas, to:

                     c/o James A. Regas
                     11 I W. Washington Street
                     Suite 1525
                     Chicago, IL 60602

                     If to Peter Pappas, Sr.:

                     Peter J. Pappas, Sr.
                     c/o PJ Mechanical
                     135 West 18th Street
                     New York, NY 10011

     5. This Amendment shall be effective when executed by persons holding at
least 50% of the Investor Registrable Securities and at least 50% of the
Registrable Securities, determined immediately prior to the effectiveness of
this Amendment. By signing this Amendment, the

                                        2

<PAGE>

holders of Investor Registrable Securities and Registrable Securities consent to
the grant of registration rights provided for herein and to this Amendment. This
Amendment may be executed in counterparts, any one of which need not contain the
signatures of more than one party, but all such counterparts shall constitute
one and the same agreement.

     6. It is expressly understood and agreed that if, at any time or under any
circumstances, any provision of this Amendment or its effect shall be deemed
invalid or unenforceable for any reason, then any or all of such invalid or
unenforceable provisions shall be amended, without any additional writing or
agreement, so as to cause such provision or its effect to be valid and enforced
to the fullest extent permitted.

                            [SIGNATURE PAGE FOLLOWS]

                                        3

<PAGE>

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

                                       ADVANTAGE BUSINESS SERVICES
                                       HOLDINGS, INC.

                                       By: /s/ Charles W. Lathrop
                                           -------------------------------------
                                           Charles W. Lathrop, Jr.
                                           President and Chief Executive Officer

                                       /s/ Chris Kapolas
                                       -----------------------------------------
                                       Chris Kapolas

                                       /s/ James Kapolas
                                       -----------------------------------------
                                       James Kapolas

                                       /s/ Mary Kapolas
                                       -----------------------------------------
                                       Mary Kapolas

                                       /s/ Peter J. Pappas
                                       -----------------------------------------
                                       Peter J. Pappas

                                       /s/ Suzanne E. Regas
                                       -----------------------------------------
                                       Suzanne E. Regas

                                       /s/ Dean J. Regas
                                       -----------------------------------------
                                       Dean J. Regas

                                       /s/ Allyson Regas
                                       -----------------------------------------
                                       Allyson Regas

                                       INVESTOR

                                       WILLIS STEIN & PARTNERS, L.P.

                                       By: Willis Stein & Partners, L.L.C.
                                           Its: General Partner

                                       By: /s/ Daniel Gill
                                           -------------------------------------
                                           Its: Managing Director

                                        4

<PAGE>

                FOURTH AMENDMENT TO REGISTRATION RIGHTS AGREEMENT
                -------------------------------------------------

     THIS FOURTH AMENDMENT TO REGISTRATION RIGHTS AGREEMENT (this "Amendment")
                                                                   ---------
entered into as of August 9, 2001 by and between ADVANTAGE BUSINESS SERVICES
HOLDINGS, INC., a Delaware corporation located at 126 Merrow Road, P.O. Box
1330, Auburn, Maine 04211-1330 (the "Company"); the Person listed on the
                                     -------
signature page hereto as "investor", and NEW ENGLAND BUSINESS SERVICE, INC., a
Delaware corporation located at 500 Main Street, Groton, Massachusetts 01471
("NEBS").
  ----

                                    RECITALS
                                    --------

     WHEREAS, the Company and certain of its Shareholders have entered into a
Registration Rights Agreement, dated as of February 10, 1998 (the "Agreement");
                                                                   ---------
which Agreement provides the parties thereto other than the Company with certain
rights to have the Company register shares of the Company's stock held by such
parties and provides further that the Company may not grant to any person
registration rights except as provided therein without the written consent of at
least 50% of the Investor Registrable Securities and that any registration
rights granted may not be inconsistent with the rights granted holders of
Registrable Securities under the Agreement; and

     WHEREAS, the Company, subsequently entered into a Registration Rights
Agreement dated as of July 23, 1999 with certain additional shareholders (the
"Second Agreement"), which Second Agreement provides such Shareholders with
 ----------------
certain rights to have the Company register shares of the Company's stock held
by them and provides further that the Company shall not thereafter enter into
any agreement which is inconsistent with the Second Agreement; and

     WHEREAS, the Company and certain of its shareholders entered into an
Amendment to Registration Rights Agreement dated as of March 23, 2000 (the
"First Amendment") in connection with the issuance to NEBS of Common
 ---------------

Stock of the Company together with Warrants to purchase additional Common Stock
of the Company which First Amendment provides that the Agreement, as amended,
may be further amended to provide registration rights which are pari passu with
the registration rights of NEBS; and

     WHEREAS, the Company and certain of its shareholders entered into an
Amendment to Registration Rights Agreement dated as of September 21, 2000 (the
"Second Amendment") in connection with the issuance to Chris Kapolas, James
 ----------------
Kapolas, Mary Kapolas, Peter J. Pappas, Sr., Suzanne E. Regas, Dean J. Regas and
Allyson Regas of Common Stock of the Company in connection with the merger of
Related Payroll Services, Inc. with and into a subsidiary of the Company; and

     WHEREAS, the Company and certain of its shareholders entered into an
Amendment to Registration Rights Agreement dated as of December 29, 2000 (the
"Third Amendment") in connection with the transfer to Melodee K. Ruffo of Common
Stock of the Company subject to the Agreement as a result of the Second
Amendment; and

<PAGE>

     WHEREAS, the Company and NEBS have this day consummated a Purchase and Sale
Agreement dated as of August 9, 2001, pursuant to which NEBS has been issued
1,069,772 shares of Common Stock of the Company together with Warrants to
purchase additional Common Stock of the Company (such presently issued shares,
together with any shares to be issued pursuant to the Warrants, being
hereinafter collectively referred to as the "New NEBS Shares"); and
                                             ---------------

     WHEREAS, the Company wishes to provide NEBS, with the same registration
rights with respect to the New NEBS Shares provided to Other Stockholders (other
than the Investors) by the Registration Rights Agreement to the extent not
inconsistent with the Second Agreement.

     NOW, THEREFORE, in consideration of the premises and the mutual promises
herein made and the recitals stated above which are incorporated into this
Amendment, and in consideration of the representations, warranties, covenants,
agreements and understandings herein contained, the Parties agree as follows:

     1. Terms not otherwise defined in this Amendment shall have the meanings
set forth in the Agreement.

     2. NEBS hereby becomes a party to the Agreement which is incorporated into
this Amendment by reference, with respect to the New NEBS shares, and agrees to
be bound by all the terms and conditions thereof, and shall have the same rights
and responsibilities thereunder as a holder of Other Stockholder Registrable
Securities and shall be one of the "Other Stockholders" for purposes of the
Agreement. Each reference in the Agreement to "Other Stockholder Registrable
Securities", or any related or derivative term, shall be deemed to include the
New NEBS Shares, except as the context may otherwise require.

     3. The Agreement shall be amended to provide that no subsequent amendment
thereto which adversely and disproportionately affects the rights of NEBS
thereunder shall be effective as to NEBS without NEBS' written consent, provided
that (i) a grant of registration rights which are pari passu with the
registration rights of NEBS and an amendment to the Agreement to add thereto as
parties the person or persons to whom such registration rights are granted and
(ii) a grant of registration rights which are superior to, or pari passu with,
the registration rights of the holders of the Investor Registrable Securities
with the written consent of the holders of at least 50% of the Investor
Registrable Securities and an amendment to the Agreement to add thereto as
parties the person or persons to whom such registration rights are granted shall
not be deemed to affect NEBS adversely.

     4. Notwithstanding anything herein to be contrary, to the extent that any
provision of this Amendment or any of the rights granted to NEBS hereunder are
inconsistent with, or violates any provision of, the Second Agreement, then the
Second Agreement shall control and each such

                                        2

<PAGE>

provision or right of NEBS shall be interpreted to the fullest extent possible
without creating such inconsistency or violation.

     5. This Amendment shall be effective when executed by persons holding at
least 50% of the Investor Registrable Securities and at least 50% of the
Registrable Securities, determined immediately prior to the effectiveness of
this Amendment. By signing this Amendment, the holders of Investor Registrable
Securities and Registrable Securities consent to the grant of registration
rights provided for herein and to this Amendment. This Amendment may be executed
in counterparts, any one of which need not contain the signatures of more than
one party, but all such counterparts shall constitute one and the same
agreement.

     6. It is expressly understood and agreed that if, at any time or under any
circumstances, any provision of this Amendment or its effect shall be deemed
invalid or unenforceable for any reason, then any or all of such invalid or
unenforceable provisions shall be amended, without any additional writing or
agreement, so as to cause such provision or its effect to be valid and enforced
to the fullest extent permitted.

                                        3

<PAGE>

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

                                      ADVANTAGE BUSINESS SERVICES
                                      HOLDINGS, INC.

                                      By: /s/ Charles W. Lathrop, Jr.
                                          --------------------------------------
                                          Charles W. Lathrop, Jr.
                                          President and Chief Executive Officer

                                      NEW ENGLAND BUSINESS SERVICE, INC.

                                      By: /s/ George P. Allman
                                          --------------------------------------
                                          George P. Allman
                                          Senior Vice President

                                      INVESTOR

                                      WILLIS STEIN & PARTNERS, L.P.

                                      By: Willis Stein & Partners, L.L.C.
                                          Its: General Partner

                                      By: /s/ Daniel Gill
                                          --------------------------------------
                                          Its: Managing Director

                                        4

<PAGE>

                   AMENDMENT TO REGISTRATION RIGHTS AGREEMENT
                   ------------------------------------------

     THIS AMENDMENT TO REGISTRATION RIGHTS AGREEMENT (this "Amendment") entered
                                                            ---------
into as of December 29, 2000 by and between ADVANTAGE BUSINESS SERVICES
HOLDINGS, INC., a Delaware corporation located at 126 Merrow Road, P.O. Box
1330, Auburn, Maine 04211-1330 (the "Company"), the Person listed on the
                                     -------
signature pages hereto as "Investor", and Melodee K. Ruffo ("Ruffo").
                                                             -----

                                    RECITALS
                                    --------

     WHEREAS, the Company and certain of its Shareholders have entered into a
Registration Rights Agreement, dated as of February 10, 1998 (the "Agreement");
                                                                   ---------
which Agreement provides the parties thereto other than the Company with certain
rights to have the Company register shares of the Company's stock held by such
parties and provides further that the Company may not grant to any person
registration rights except as provided therein without the written consent of
the holders of at least 50% of the Investor Registrable Securities and that any
registration rights granted may not be inconsistent with the rights granted
holders of Registrable Securities under the Agreement; and

     WHEREAS, the Company, subsequently entered into a Registration Rights
Agreement dated as of July 23, 1999 with certain additional shareholders (the
"Second Agreement"), which Second Agreement provides such Shareholders with
 -----------------
certain rights to have the Company register shares of the Company's stock held
by them and provides further that the Company shall not thereafter enter into
any agreement which is inconsistent with the Second Agreement; and

     WHEREAS, the Company and certain of its shareholders entered into an
Amendment to Registration Rights Agreement dated as of March 23, 2000 (the
"Third Agreement") in connection with the issuance to New England Business
 ---------------
Service, Inc. ("NEBS") of Common Stock of the Company together with Warrants to
                ----
purchase additional Common Stock of the Company which Third Agreement provides
that the Agreement, as amended, may be further amended to provide registration
rights which are pari passu with the registration rights of NEBS;

     WHEREAS, Ruffo has received as a gift shares of Company Common Stock (the
"Shares") from Mary Kapolas, her mother ("Kapolas");

     WHEREAS, the Company and certain of its shareholders, including Kapolas,
entered into an Amendment to Registration Rights Agreement dated as of September
21, 2000 (the "Fourth Agreement") in connection with the merger of Related
Payroll Services, Inc. ("RPS") with and into a subsidiary of the Company and the
issuance of Common Stock of the Company to the shareholders of RPS, including
Kapolas;

     WHEREAS, the Company wishes to provide Ruffo, with the same registration
rights with respect to the Shares as had been provided to Kapolas and Other
Stockholders (other than the

<PAGE>

Investors) by the Agreement, as amended, to the extent not inconsistent with the
Second Agreement, Third Agreement and Fourth Agreement.

     NOW, THEREFORE, in consideration of the premises and the mutual promises
herein made and the recitals stated above which are incorporated into this
Amendment, and in consideration of the representations, warranties, covenants,
agreements and understandings herein contained, the Parties agree as follows:

     1. Terms not otherwise defined in this Amendment shall have the meanings
set forth in the Agreement.

     2. Ruffo hereby becomes a party to the Agreement, which is incorporated
into this Amendment by reference, and agrees to be bound by all the terms and
conditions thereof, and shall have the same rights and responsibilities
thereunder as a holder of Other Stockholder Registrable Securities and shall be
one of the "Other Stockholders" for purposes of the Agreement. Each reference in
the Agreement to "Other Stockholder Registrable Securities", or any related or
derivative term, shall be deemed to include the Shares, except as the context
may otherwise require.

     3. Notwithstanding anything herein to be contrary, to the extent that any
provision of this Amendment or any of the rights granted to the Sellers
hereunder are inconsistent with, or violates any provision of, the Second
Agreement, then the Second Agreement shall control and each such provision or
right of the Sellers shall be interpreted to the fullest extent possible without
creating such inconsistency or violation.

     4. The "Registration Rights Agreement Notices Schedule" attached at the end
of the Agreement shall be amended by the addition thereto of the following:

                              If to Melodee K. Ruffo, to:

                              Melodee K. Ruffo
                              c/o James Kapolas
                              126 Forest Trail
                              Oak Brook, IL 60521

     5. This Amendment shall be effective when executed by persons holding at
least 50% of the Investor Registrable Securities and at least 50% of the
Registrable Securities, determined immediately prior to the effectiveness of
this Amendment. By signing this Amendment, the holders of Investor Registrable
Securities and Registrable Securities consent to the grant of registration
rights provided for herein and to this Amendment. This Amendment may be executed
in counterparts, any one of which need not contain the signatures of more than
one party, but all such counterparts shall constitute one and the same
agreement.

     6. It is expressly understood and agreed that if, at any time or under any
circumstances, any provision of this Amendment or its effect shall be deemed
invalid or unenforceable for any reason, then any or all of such invalid or
unenforceable provisions shall be amended, without any additional writing or
agreement, so as to cause such provision or its effect to be valid and enforced
to the fullest extent permitted.

                                        2

<PAGE>

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

                                      ADVANTAGE BUSINESS SERVICES
                                      HOLDINGS, INC.

                                      By: /s/ Charles W. Lathrop, Jr.
                                          --------------------------------------
                                          Charles W. Lathrop, Jr.
                                          President and Chief Executive Officer

                                      /s/ Melodee K. Ruffo
                                      ------------------------------------------
                                      Melodee K. Ruffo

                                      INVESTOR

                                      WILLS STEIN & PARTNERS, L.P.

                                      By: Willis Stein & Partners, L.L.C.
                                          Its: General Partner

                                      By: /s/ Daniel Gill
                                          --------------------------------------
                                          Its: Managing Director

                                       3

Source: [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00038-of-00352.parquet"}, [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00038-of-00352.parquet"}]]