<PAGE>
 
                                                                   Exhibit 10.12


                                 AGREEMENT
                                 ---------

          THIS AGREEMENT dated as of January 30, 1997, is made by and between
Metromail Corporation, a Delaware corporation ("Metromail"; Metromail and its
Subsidiaries being hereafter referred to as the "Company"), and Susan L.
Henricks (the "Executive").

          WHEREAS the Company considers it essential to the best interests of
its stockholders to foster the continuous employment of key management
personnel; and

          WHEREAS the Board of Directors of Metromail (the "Board") recognizes
that, as is the case with many publicly held corporations, the possibility of a
Change in Control (as defined in the last Section hereof) exists and that such
possibility, and the uncertainty and questions which it may raise among
management, may result in the departure or distraction of management personnel
to the detriment of the Company and its stockholders; and

          WHEREAS the Board has determined that appropriate steps should be
taken to reinforce and encourage the continued attention and dedication of
members of the Company's management, including the Executive, to their assigned
duties without distraction in the face of potentially disturbing circumstances
arising from the possibility of a Change in Control;
<PAGE>
 
          NOW THEREFORE, in consideration of the promises and the mutual
covenants herein contained, the Company and the Executive hereby agree as
follows:

          1.  Defined Terms.  The definition of capitalized terms used in this
Agreement is provided in the last Section hereof.

          2.  Term of Agreement.  (a) This Agreement shall commence on the date
hereof and shall continue until terminated by the Company as provided in
paragraph (b) of this Section 2; provided, however, that this Agreement shall
terminate in any event upon the first to occur of (i) the Executive's death and
(ii) termination of the Executive's employment with the Company prior to a
Change in Control.

          (b) The Company shall have the right prior to a Change in Control, in
its sole discretion, pursuant to action by the Board, to approve the termination
of this Agreement, which termination shall not become effective until the date
fixed by the Board for such termination, which date shall be at least 120 days
after notice thereof is given by the Company to the Executive in accordance with
Section 10 hereof; provided, however, that no such action shall be taken by the
Board during any period of time when the Board has knowledge that any Person has
taken steps reasonably calculated to effect a Change in Control until, in the
opinion of the Board, such Person has 

                                      -2-
<PAGE>
 
abandoned or terminated its efforts to effect a Change in Control; and provided
further, that in no event shall this Agreement be terminated in the event of a
Change in Control.

          3.  Company's Covenants Summarized.  In order to induce the Executive
to remain in the employ of the Company and in consideration of the Executive's
covenants set forth in Section 4 hereof, the Company agrees, under the
conditions described herein, to pay the Executive the Severance Payments and the
other payments and benefits described herein in the event the Executive's
employment with the Company is terminated following a Change in Control and
during the term of this Agreement.  No amount or benefit shall be payable under
this Agreement unless there shall have been (or, under the terms hereof, there
shall be deemed to have been) a termination of the Executive's employment with
the Company following a Change in Control.  This Agreement shall not be
construed as creating an express or implied contract of employment and, except
as otherwise agreed in writing between the Executive and the Company, the
Executive shall not have any right to be retained in the employ of the Company.

          4.  The Executive's Covenants.  The Executive agrees that, subject to
the terms and conditions of this Agreement, in the event of a Potential Change
in Control during the term of this Agreement, the Executive will remain in the
employ of the Company until the earliest of (i) a date which is six (6) months

                                      -3-
<PAGE>
 
from the date of such Potential Change of Control, (ii) the date of a Change in
Control, (iii) the date of termination by the Executive of the Executive's
employment for Good Reason (determined by treating the Potential Change in
Control as a Change in Control in applying the definition of Good Reason), by
reason of death, Disability or Retirement, or (iv) the termination by the
Company of the Executive's employment for any reason.

          5.  Compensation Other Than Severance Payments.
              ------------------------------------------ 

          5.01  Following a Change in Control and during the term of this
Agreement, during any period that the Executive fails to perform the Executive's
full-time duties with the Company as a result of incapacity due to physical or
mental illness, the Company shall pay the Executive's full salary to the
Executive at the rate in effect at the commencement of any such period, together
with all compensation and benefits payable to the Executive under the terms of
any compensation or benefit plan, program or arrangement maintained by the
Company during such period, until the Executive's employment is terminated by
the Company for Disability.

          5.02  If the Executive's employment shall be terminated for any reason
following a Change in Control and during the term of this Agreement, the Company
shall pay the Executive's full salary to the Executive through the Date of

                                      -4-
<PAGE>
 
Termination at the rate in effect at the time the Notice of Termination is
given, together with all compensation and benefits payable to the Executive
through the Date of Termination under the terms of any compensation or benefit
plan, program or arrangement maintained by the Company during such period.

          5.03  If the Executive's employment shall be terminated for any reason
following a Change in Control and during the term of this Agreement, the Company
shall pay the Executive's normal post-termination compensation and benefits to
the Executive as such payments become due; provided that, in no event shall any
severance pay which might be payable to the Executive pursuant to the Company's
Separation Pay Plan be paid if the Executive is entitled to the Severance
Payments as a result of such termination.  Such post-termination compensation
and benefits shall be determined under, and paid in accordance with, the
Company's retirement, insurance and other compensation or benefit plans,
programs and arrangements.

          6.  Severance Payments.
              ------------------ 

          6.01  The Company shall pay the Executive the payments described in
this Section 6.01 (the "Severance Payments") upon the termination of the
Executive's employment following a Change in Control and during the term of this
Agreement, in addition to the payments and benefits described in Section 5
hereof, unless such termination is (i) by the Company for Cause, (ii) by reason

                                      -5-
<PAGE>
 
of death or Disability or (iii) by the Executive without Good Reason; provided,
however, that the Company shall pay the Executive the Severance Payments, in
addition to the payments and benefits described in Section 5 hereof, if the
Executive's employment is terminated by the Executive for any reason whatsoever
during the Window Period. The Executive's employment shall be deemed to have
been terminated following a Change in Control by the Company without Cause or by
the Executive with Good Reason if the Executive's employment is terminated prior
to a Change in Control without Cause at the direction of a Person who has
entered into an agreement with the Company the consummation of which will
constitute a Change in Control or if the Executive terminates his employment
with Good Reason prior to a Change in Control (determined by treating a
Potential Change in Control as a Change in Control in applying the definition of
Good Reason) if the circumstance or event which constitutes Good Reason occurs
at the direction of such Person.

          (A) In lieu of any further salary payments to the Executive for
periods subsequent to the Date of Termination and in lieu of any severance
benefit otherwise payable to the Executive, the Company shall pay to the
Executive a lump sum severance payment, in cash, equal to the amount of three
(3) times the Executive's Planned Compensation.

                                      -6-
<PAGE>
 
          (B) In addition to the retirement benefits to which the Executive is
entitled under the Pension Plan or any successor plans thereto, the Company
shall pay the Executive a lump sum amount, in cash, equal to the actuarial
equivalent of the excess of (i) the retirement pension (determined as a straight
life annuity commencing at Normal Retirement Age) which the Executive would have
accrued under the terms of the Pension Plan (without regard to any amendment to
the Pension Plan made subsequent to a Change in Control and on or prior to the
Date of Termination, which amendment adversely affects in any manner the
computation of retirement benefits thereunder), determined as if the Executive
were fully vested thereunder and had accumulated (after the Date of Termination)
thirty-six (36) (or, if less, a number equal to the number of months, including
fractional parts thereof, from the Date of Termination until the Executive
reaches Normal Retirement Age) additional months of service credit thereunder at
the Executive's highest annual rate of compensation during the twelve (12)
months immediately preceding the Date of Termination, and (ii) the retirement
pension (determined as a straight life annuity commencing at Normal Retirement
Age) which the Executive had then accrued pursuant to the provisions of the
Pension Plan.  For purposes of this Section 6.01(B), "actuarial equivalent"
shall be determined using the same assumptions

                                      -7-
<PAGE>
 
utilized under the Pension Plan immediately prior to the Date of Termination.

          (C) For a thirty-six (36) month period after the Date of Termination,
the Company shall arrange to provide the Executive with life, disability,
accident and health insurance benefits substantially similar to those which the
Executive is receiving immediately prior to the Notice of Termination (without
giving effect to any reduction in such benefits subsequent to a Change in
Control which reduction constitutes Good Reason); provided, however, that, in
the event the date upon which the Executive attains Normal Retirement Age occurs
during such thirty-six (36) month period, the Executive shall thereafter receive
such life, disability, accident and health insurance benefits as would be
provided to him as a retiree.  Benefits otherwise receivable by the Executive
pursuant to this Section 6.01(C) shall be reduced to the extent comparable
benefits are actually received by or made available to the Executive without
cost during the thirty-six (36) month period following the Executive's
termination of employment (and any such benefits actually received by the
Executive shall be reported to the Company by the Executive).

          6.02  (A) Whether or not the Executive becomes entitled to the
Severance Payments, if any of the Total Payments will be subject to the Excise
Tax, the Company shall pay to the Executive 

                                      -8-
<PAGE>
 
an additional amount (the "Gross-Up Payment") such that the net amount retained
by the Executive, after deduction of any Excise Tax on the Total Payments and
any federal, state and local income tax and Excise Tax upon the payment provided
for by this Section 6.02, shall be equal to the excess of the Total Payments
over the payment provided for by this Section 6.02.

          (B) For purposes of determining whether any of the Total Payments will
be subject to the Excise Tax and the amount of such Excise Tax, (i) any payments
or benefits received or to be received by the Executive in connection with a
Change in Control or the Executive's termination of employment (whether pursuant
to the terms of this Agreement or any other plan, arrangement or agreement with
the Company, any Person whose actions result in a Change in Control or any
Person affiliated with the Company or such Person) (the "Total Payments") shall
be treated as "parachute payments" (within the meaning of section 28OG(b) (2) of
the Code) unless, in the opinion of tax counsel selected by the Company's
independent auditors and reasonably acceptable to the Executive, such payments
or benefits (in whole or in part) do not constitute parachute payments,
including by reason of section 280G(b) (4) (A) of the Code, and all "excess
parachute payments" (within the meaning of section 280G(b) (1) of the Code)
shall be treated as subject to the Excise Tax unless, in the opinion of such tax
counsel, such excess parachute 

                                      -9-
<PAGE>
 
payments (in whole or in part) represent reasonable compensation for services
actually rendered (within the meaning of section 280G(b) (4) (B) of the Code),
or are otherwise not subject to the Excise Tax, and (ii) the value of any
noncash benefits or any deferred payment or benefit shall be determined by the
Company's independent auditors in accordance with the principles of sections
280G(d)(3) and (4) of the Code. For purposes of determining the amount of the
Gross-Up Payment, the Executive shall be deemed to pay federal income taxes at
the highest marginal rate of federal income taxation in the calendar year in
which the Gross-Up Payment is to be made and state and local income taxes at the
highest marginal rate of taxation in the state and locality of the Executive's
residence on the Date of Termination, net of the maximum reduction in federal
income taxes which could be obtained from deduction of such state and local
taxes.

          (C) In the event that the Excise Tax is subsequently determined to be
less than the amount taken into account hereunder at the time of termination of
the Executive's employment, the Executive shall repay to the Company, at the
time that the amount of such reduction in Excise Tax is finally determined, the
portion of the Gross-Up Payment attributable to such reduction (plus that
portion of the Gross-Up Payment attributable to the Excise Tax and federal,
state and local 

                                      -10-
<PAGE>
 
income tax imposed on the Gross-Up Payment being repaid by the Executive to the
extent that such repayment results in a reduction in Excise Tax and/or a
federal, state or local income tax deduction) plus interest on the amount of
such repayment at the rate provided in section 1274(b)(2)(B) of the Code. In the
event that the Excise Tax is determined to exceed the amount taken into account
hereunder at the time of the termination of the Executive's employment
(including increases in the Excise Tax resulting from any payment the existence
or amount of which could not be determined at the time of the Gross-Up Payment),
the Company shall make an additional Gross-Up Payment in respect of such excess
(plus any interest, penalties or additions payable by the Executive with respect
to such excess) at the time that the amount of such excess is finally
determined. The Executive and the Company shall each reasonably cooperate with
the other in connection with any administrative or judicial proceedings
concerning the existence or amount of liability for Excise Tax with respect to
the Total Payments.

          6.03  The payments provided for in Section 6.01 (other than Section
6.01(C)) and 6.02 hereof shall be made not later than the fifth (5th) day
following the Date of Termination; provided, however, that, if the amounts of
such payments cannot be finally determined on or before such day, the Company
shall pay to the Executive on such day an estimate, as determined in 

                                      -11-
<PAGE>
 
good faith by the Company, of the minimum amount of such payments to which the
Executive is clearly entitled and shall pay the remainder of such payments
(together with interest at the rate provided in section 1274(b)(2)(B) of the
Code) as soon as the amount thereof can be determined but in no event later than
the thirtieth (30th) day after the Date of Termination. In the event that the
amount of the estimated payments exceeds the amount subsequently determined to
have been due, such excess shall constitute a loan by the Company to the
Executive, payable on the fifth (5th) business day after demand by the Company
(together with interest at the rate provided in section 1274(b)(2)(B) of the
Code). At the time that payments are made under this Section, the Company shall
provide the Executive with a written statement setting forth the manner in which
such payments were calculated and the basis for such calculations including,
without limitation, any opinions or other advice the Company has received from
outside counsel, auditors or consultants (and any such opinions or advice which
are in writing shall be attached to the statement).

          6.04  The Company also shall pay to the Executive all legal fees and
expenses incurred by the Executive as a result of a termination which entitles
the Executive to the Severance Payments (including all such fees and expenses,
if any, incurred in disputing any such termination or in seeking in good faith
to 

                                      -12-
<PAGE>
 
obtain or enforce any benefit or right provided by this Agreement or in
connection with any tax audit or proceeding to the extent attributable to the
application of section 4999 of the Code to any payment or benefit provided
hereunder).  Such payments shall be made within five (5) business days after
delivery of the Executive's written requests for payment accompanied with such
evidence of fees and expenses incurred as the Company reasonably may require.

          7.  Termination Procedures and Compensation During Dispute.
              ------------------------------------------------------ 

          7.01  Notice of Termination.  After a Change in Control and during the
term of this Agreement, any purported termination of the Executive's employment
(other than by reason of death) shall be communicated by written Notice of
Termination from one party hereto to the other party hereto in accordance with
Section 10 hereof.  For purposes of this Agreement, a "Notice of Termination"
shall mean a notice which shall indicate the specific termination provision in
this Agreement relied upon and, except for a termination during the Window
Period, shall set forth in reasonable detail the facts and circumstances claimed
to provide a basis for termination of the Executive's employment under the
provision so indicated.  Further, a Notice of Termination for Cause is required
to include a copy of a resolution duly adopted by the affirmative vote of not
less than 

                                      -13-
<PAGE>
 
three-quarters (3/4) of the entire membership of the Board at a meeting of the
Board which was called and held for the purpose of considering such termination
(after reasonable notice to the Executive and an opportunity for the Executive,
together with the Executive's counsel, to be heard before the Board) finding
that, in the good faith opinion of the Board, the Executive was guilty of
conduct set forth in clause (i) or (ii) of the definition of Cause herein, and
specifying the particulars thereof in detail.

          7.02  Date of Termination.  "Date of Termination," with respect to any
purported termination of the Executive's employment after a Change in Control
and during the term of this Agreement, shall mean (i) if the Executive's
employment is terminated for Disability, thirty (30) days after Notice of
Termination is given (provided that the Executive shall not have returned to the
full-time performance of the Executive's duties during such thirty (30) day
period), and (ii) if the Executive's employment is terminated for any other
reason, the date specified in the Notice of Termination (which, in the case of a
termination by the Company, shall not be less than thirty (30) days (except in
the case of a termination for Cause) and, in the case of a termination by the
Executive, shall not be less than fifteen (15) days (except in the case of a
termination during the Window Period) nor more than sixty (60) days,
respectively, from the date such Notice of Termination is given).

                                      -14-
<PAGE>
 
          7.03  Dispute Concerning Termination.  If within fifteen (15) days
after any Notice of Termination is given, or, if later, prior to the Date of
Termination (as determined without regard to this Section 7.03), the party
receiving such Notice of Termination notifies the other party that a dispute
exists concerning the termination, the Date of Termination shall be the date on
which the dispute is finally resolved, either by mutual written agreement of the
parties or by a final judgment, order or decree (which is not appealable or with
respect to which the time for appeal therefrom has expired and no appeal has
been perfected) of a court of competent jurisdiction; provided, however, that
the Date of Termination shall be extended by a notice of dispute only if such
notice is given in good faith and the party giving such notice pursues the
resolution of such dispute with reasonable diligence.

          7.04  Compensation During Dispute.  If a purported termination occurs
following a Change in Control and during the term of this Agreement, and such
termination is disputed in accordance with Section 7.03 hereof, the Company
shall continue to pay the Executive the full compensation in effect when the
notice giving rise to the dispute was given (including, but not limited to,
salary) and continue the Executive as a participant in all compensation, benefit
and insurance plans in which the Executive was participating when the notice
giving rise to the 

                                      -15-
<PAGE>
 
dispute was given, until the dispute is finally resolved in accordance with
Section 7.03 hereof. Amounts paid under this Section 7.04 are in addition to all
other amounts due under this Agreement (other than those due under Section 5.02
hereof) and shall not be offset against or reduce any other amounts due under
this Agreement.

          8.  No Mitigation.  The Company agrees that, if the Executive's
employment by the Company is terminated during the term of this Agreement, the
Executive is not required to seek other employment or to attempt in any way to
reduce any amounts payable to the Executive by the Company pursuant to Section 6
or Section 7.04 hereof.  Further, the amount of any payment or benefit provided
for in Section 6 (other than Section 6.01(C)) or Section 7.04 hereof shall not
be reduced by any compensation earned by the Executive as the result of
employment by another employer, by retirement benefits, by offset against any
amount claimed to be owed by the Executive to the Company, or otherwise.

          9.  Successors; Binding Agreement.
              ----------------------------- 

          9.01  In addition to any obligations imposed by law upon any successor
to Metromail, Metromail will require any successor (whether direct or indirect,
by purchase, merger, consolidation or otherwise) to all or substantially all of
the business or assets of Metromail to expressly assume and agree to perform
this Agreement in the same manner and to the same extent that 

                                      -16-
<PAGE>
 
Metromail would be required to perform it if no such succession had taken place.
Failure of Metromail to obtain such assumption and agreement prior to the
effectiveness of any such succession shall be a breach of this Agreement and
shall entitle the Executive to compensation in the same amount and on the same
terms as the Executive would be entitled to hereunder if the Executive were to
terminate the Executive's employment for Good Reason after a Change in Control,
except that, for purposes of implementing the foregoing, the date on which any
such succession becomes effective shall be deemed the Date of Termination.

          9.02  This Agreement shall inure to the benefit of and be enforceable
by the Executive's personal or legal representatives, executors, administrators,
successors, heirs, distributees, devisees and legatees.  If the Executive shall
die while any amount would still be payable to the Executive hereunder (other
than amounts which, by their terms, terminate upon the death of the Executive)
if the Executive had continued to live, all such amounts, unless otherwise
provided herein, shall be paid in accordance with the terms of this Agreement to
the executors, personal representatives or administrators of the Executive's
estate.

          10.  Notices.  For the purpose of this Agreement, notices and all
other communications provided for in this Agreement shall be in writing and
shall be deemed to have been 

                                      -17-
<PAGE>
 
duly given when delivered or mailed by United States registered mail, return
receipt requested, postage prepaid, addressed to the respective addresses set
forth below, or to such other address as either party may have furnished to the
other in writing in accordance herewith, except that notice of change of address
shall be effective only upon actual receipt:

          To the Company:

          Metromail Corporation
          360 East 22nd Street
          Lombard, IL  60148
          Attention: General Counsel

          To the Executive:

          Susan L. Henricks

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

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

          11.  Miscellaneous.  No provision of this Agreement may be modified,
waived or discharged unless such waiver, modification or discharge is agreed to
in writing and signed by the Executive and such officer as may be specifically
designated by the Board.  No waiver by either party hereto at any time of any
breach by the other party hereto of, or compliance with, any condition or
provision of this Agreement to be performed by such other party shall be deemed
a waiver of similar or dissimilar provisions or conditions at the same or at any
prior or subsequent time.  No agreements or representations, oral or otherwise,
express or implied, with respect to the subject matter hereof have been made by
either party which are not expressly set 

                                      -18-
<PAGE>
 
forth in this Agreement. The validity, interpretation, construction and
performance of this Agreement shall be governed by the laws of the State of
Illinois. All references to sections of the Exchange Act or the Code shall be
deemed also to refer to any successor provisions to such sections. Any payments
provided for hereunder shall be paid net of any applicable withholding required
under federal, state or local law and any additional withholding to which the
Executive has agreed. The obligations of the Company and the Executive under
Sections 6 and 7 hereof shall survive the expiration of the term of this
Agreement.

          12.  Validity.  The invalidity or unenforceability or any provision of
this Agreement shall not affect the validity or enforceability of any other
provision of this Agreement, which shall remain in full force and effect.

          13.  Counterparts.  This Agreement may be executed in several
counterparts, each of which shall be deemed to be an original but all of which
together will constitute one and the same instrument.

          14.  Settlement of Disputes; Arbitration.  All claims by the Executive
for benefits under this Agreement shall be directed to and determined by the
Board and shall be in writing.  Any denial by the Board of a claim for benefits
under this Agreement shall be delivered to the Executive in writing and shall
set forth the specific reasons for the denial and the 

                                      -19-
<PAGE>
 
specific provisions of this Agreement relied upon. The Board shall afford a
reasonable opportunity to the Executive for a review of the decision denying a
claim and shall further allow the Executive to appeal to the Board a decision of
the Board within sixty (60) days after notification by the Board that the
Executive's claim has been denied. Any further dispute or controversy arising
under or in connection with this Agreement shall be settled exclusively by
arbitration in Chicago, Illinois, in accordance with the rules of the American
Arbitration Association then in effect. Judgment may be entered on the
arbitrator's award in any court having jurisdiction; provided, however, that the
Executive shall be entitled to seek specific performance of the Executive's
right to be paid until the Date of Termination during the pendency of any
dispute or controversy arising under or in connection with this Agreement.

          15.  Definitions.  For purposes of this Agreement, the following terms
shall have the meanings indicated below:

          (A) "Beneficial Owner" shall have the meaning defined in Rule 13d-3
under the Exchange Act.

          (B) "Board" shall mean the Board of Directors of Metromail.

          (C) "Bonus Plan" shall mean any supplementary compensation plan or
bonus plan or arrangement, or any similar successor plan or arrangement,
applicable to the Executive, other 

                                      -20-
<PAGE>
 
than the 1996 Stock Incentive Plan and the 1996 Broad-Based Employee Stock Plan.

          (D) "Cause" for termination by the Company of the Executive's
employment, after any Change in Control, shall mean (i) the willful and
continued failure by the Executive to substantially perform the Executive's
duties with the Company (other than any such failure resulting from the
Executive's incapacity due to physical or mental illness or any such actual or
anticipated failure after the issuance of a Notice of Termination for Good
Reason by the Executive pursuant to Section 7.01 hereof) after a written demand
for substantial performance is delivered to the Executive by the Board, which
demand specifically identifies the manner in which the Board believes that the
Executive has not substantially performed the Executive's duties, or (ii) the
willful engaging by the Executive in conduct which is demonstrably and
materially injurious to the Company, monetarily or otherwise.  For purposes of
clauses (i) and (ii) of this definition, no act, or failure to act, on the
Executive's part shall be deemed "willful" unless done, or omitted to be done,
by the Executive not in good faith and without reasonable belief that the
Executive's act, or failure to act, was in the best interest of the Company.

                                      -21-
<PAGE>
 
          (E) A "Change in Control" shall be deemed to have occurred if the
conditions set forth in any one of the following paragraphs shall have been
satisfied:

               (I) any Person is or becomes the Beneficial Owner, directly or
     indirectly, of securities of Metromail (not including in the securities
     beneficially owned by such Person any securities acquired directly from
     Metromail or its affiliates) representing 50% or more of the combined
     voting power of Metromail's then outstanding securities; or

               (II) during any period of two (2) consecutive years (not
     including any period prior to the execution of this Agreement), individuals
     who at the beginning of such period constitute the Board and any new
     director (other than a director designated by a Person who has entered into
     an agreement with Metromail to effect a transaction described in clause
     (I), (III) or (IV) of this paragraph) whose election by the Board or
     nomination for election by Metromail's stockholders was approved by a vote
     of at least two-thirds (2/3) of the directors then still in office who
     either were directors at the beginning of the period or whose election or
     nomination for election was previously so approved (a "Continuing
     Director"), cease for any reason to constitute a majority thereof; or

                                      -22-
<PAGE>
 
               (III) the stockholders of Metromail approve a merger or
     consolidation of Metromail with any other corporation, other than (i) a
     merger or consolidation which would result in the voting securities of
     Metromail outstanding immediately prior thereto continuing to represent
     (either by remaining outstanding or by being converted into voting
     securities of the surviving entity), in combination with the ownership of
     any trustee or other fiduciary holding securities under an employee benefit
     plan of the Company, at least 50% of the combined voting power of the
     voting securities of Metromail or such surviving entity outstanding
     immediately after such merger or consolidation, or (ii) a merger or
     consolidation effected to implement a recapitalization of Metromail (or
     similar transaction) in which no Person acquires more than 50% of the
     combined voting power of the Company's then outstanding securities; or

               (IV) the stockholders of Metromail approve a plan of complete
     liquidation of Metromail or an agreement for the sale or disposition by
     Metromail of all or substantially all Metromail's assets.

          The foregoing to the contrary notwithstanding, a Change in Control
shall not be deemed to have occurred with respect to the Executive if (i) the
event first giving rise to the Potential 

                                      -23-
<PAGE>
 
Change in Control involves a publicly announced transaction or publicly
announced proposed transaction which at the time of the announcement has not
been previously approved by the Board and (ii) the Executive is "part of a
purchasing group" proposing the transaction. A Change in Control shall also not
be deemed to have occurred with respect to the Executive if the Executive is
part of a purchasing group which consummates the Change in Control transaction.
The Executive shall be deemed "part of a purchasing group" for purposes of the
two preceding sentences if the Executive is an equity participant or has agreed
to become an equity participant in the purchasing company or group (except for
(i) passive ownership of less than 5% of the stock of the purchasing company or
(ii) ownership of equity participation in the purchasing company or group which
is otherwise not deemed to be significant, as determined prior to the Change in
Control by a majority of the nonemployee Continuing Directors).

          (F) "Code" shall mean the Internal Revenue Code of 1986, as amended
from time to time.

          (G) "Company" shall mean Metromail and its Subsidiaries.

          (H) "Date of Termination" shall have the meaning stated in Section
7.02 hereof.

                                      -24-
<PAGE>
 
          (I) "Disability" shall be deemed the reason for the termination by the
Company of the Executive's employment, if, as a result of the Executive's
incapacity due to physical or mental illness, the Executive shall have been
absent from the full-time performance of the Executive's duties with the Company
for a period of six (6) consecutive months, the Company shall have given the
Executive a Notice of Termination for Disability, and, within thirty (30) days
after such Notice of Termination is given, the Executive shall not have returned
to the full-time performance of the Executive's duties.

          (J) "Exchange Act" shall mean the Securities Exchange Act of 1934, as
amended from time to time.

          (K) "Excise Tax" shall mean any excise tax imposed under section 4999
of the Code.

          (L) "Executive" shall mean the individual named in the first paragraph
of this Agreement.

          (M) "Good Reason" for termination by the Executive of the Executive's
employment shall mean the occurrence (without the Executive's express written
consent) of any one of the following acts by the Company, or failures by the
Company to act, unless, in the case of any act or failure to act described in
paragraph (I), (V), (VI), (VII), or (VIII) below, such act or failure to act is
corrected prior to the Date of Termination specified in the Notice of
Termination given in respect thereof:

                                      -25-
<PAGE>
 
               (I) the assignment to the Executive of any duties inconsistent
     with the Executive's status as a senior officer of the Company or a
     substantial adverse alteration in the nature or status of the Executive's
     responsibilities from those in effect immediately prior to the Change in
     Control;
               (II) a reduction by the Company in the Executive's annual base
     salary as in effect on the date hereof or as the same may be increased from
     time to time;

               (III)  the Company's requiring that the Executive's principal
     place of business be at an office located more than 25 miles from the site
     of the Executive's principal place of business immediately prior to the
     Change in Control except for required travel on the Company's business to
     an extent substantially consistent with the Executive's present business
     travel obligations;

               (IV) the failure by the Company, without the Executive's consent,
     to pay to the Executive any portion of the Executive's current
     compensation, or to pay to the Executive any portion of an installment of
     deferred compensation under any deferred compensation program of the
     Company, within seven (7) days of the date such compensation is due;

               (V) the failure by the Company to continue in effect any
     compensation plan in which the Executive 

                                      -26-
<PAGE>
 
     participates immediately prior to the Change in Control which is material
     to the Executive's total compensation, including but not limited to the
     Stock Plans, or any substitute plans adopted prior to the Change in
     Control, unless an equitable arrangement (embodied in an ongoing substitute
     or alternative plan) has been made with respect to such plan, or the
     failure by the Company to continue the Executive's participation therein
     (or in such substitute or alternative plan) on a basis not materially less
     favorable, both in terms of the amount of benefits provided and the level
     of the Executive's participation relative to other participants, as existed
     at the time of the Change in Control;

               (VI) the failure by the Company to continue to provide the
     Executive with benefits substantially similar to those enjoyed by the
     Executive under any of the Company's pension, life insurance, medical,
     health and accident, or disability plans in which the Executive was
     participating at the time of the Change in Control, the taking of any
     action by the Company which would directly or indirectly materially reduce
     any of such benefits or deprive the Executive of any material fringe
     benefit enjoyed by the Executive at the time of the Change in Control, or
     the failure by the Company to provide the Executive with the number of paid
     vacation days 

                                      -27-
<PAGE>
 
     to which the Executive is entitled on the basis of years of service with
     the Company in accordance with the Company's normal vacation policy in
     effect at the time of the Change in Control; or

               (VII) any purported termination of the Executive's employment
     which is not effected pursuant to a Notice of Termination satisfying the
     requirements of Section 9.01 hereof; for purposes of this Agreement, no
     such purported termination shall be effective.

          The Executive's right to terminate the Executive's employment for Good
Reason shall not be affected by the Executive's incapacity due to physical or
mental illness.  The Executive's continued employment shall not constitute
consent to, or a waiver of rights with respect to, any act or failure to act
constituting Good Reason hereunder.

          (N) "Gross-Up Payment" shall have the meaning given in Section 6.02
hereof.

          (O) "Metromail" shall mean Metromail Corporation and any successor to
its business or assets which assumes and agrees to perform this Agreement by
operation of law, or otherwise (except in determining, under Section 15(F)
hereof, whether or not any Change in Control of Metromail has occurred in
connection with such succession).

                                      -28-
<PAGE>
 
          (P) "Normal Retirement Age" shall mean the earliest age at which the
Executive may commence Retirement and become entitled to an unreduced pension
under the Pension Plan.

          (Q) "Notice of Termination" shall have the meaning stated in Section
7.01 hereof.

          (R) "Pension Plan" shall mean the Metromail Corporation Pension Plan.

          (S) "Person" shall have the meaning given in Section 3(a)(9) of the
Exchange Act, as modified and used in Sections 13(d) and 14(d) thereof;
provided, however, that a Person shall not include (i) Metromail or any of its
Subsidiaries, (ii) a trustee or other fiduciary holding securities under an
employee benefit plan of the Company, (iii) an underwriter temporarily holding
securities pursuant to an offering of such securities, or (iv) a corporation
owned, directly or indirectly, by the stockholders of Metromail in substantially
the same proportions as their ownership of stock of Metromail.

          (T) "Planned Compensation" shall mean the annual "planned
compensation" approved by the Board or an authorized committee thereof to be
paid to the Executive (or, if the Executive's "planned compensation" is not
presented for approval by the Board or an authorized committee thereof, then as
otherwise established by Metromail or one of its Subsidiaries) with respect to
the year in which the Date of Termination occurs, 

                                      -29-
<PAGE>
 
or with respect to either of the previous two (2) calendar years, whichever is
highest, such "planned compensation" being a gross amount comprised of base
salary plus any bonus payable to the Executive under any Bonus Plan for the
calendar year in question, assuming achievement of the maximum target level for
the period with respect to which such bonus was paid.

          (U) a "Potential Change in Control" shall be deemed to have occurred
if the conditions set forth in any one of the following paragraphs shall have
been satisfied:
               (I) Metromail enters into an agreement, the consummation of which
     would result in the occurrence of a Change in Control;

               (II) Metromail or any Person publicly announces an intention to
     take or to consider taking actions which, if consummated, would constitute
     a Change in Control;

               (III)  any Person who is or becomes the Beneficial Owner,
     directly or indirectly, of securities of Metromail representing at least 9-
     1/2% or more of the combined voting power of Metromail's then outstanding
     securities increases such Person's beneficial ownership of such securities
     by 5% or more over the percentage so owned by such Person on the date
     hereof; or

                                      -30-
<PAGE>
 
               (IV) the Board adopts a resolution to the effect that, for
     purposes of this Agreement, a Potential Change in Control has occurred.

          (V) "Retirement" shall be deemed the reason for the termination by the
Company or the Executive of the Executive's employment if such employment is
terminated in accordance with the Company's retirement policy, not including
early retirement, generally applicable to its salaried employees, as in effect
immediately prior to the Change in Control, or in accordance with any retirement
arrangement established with the Executive's consent with respect to the
Executive.

          (W) "Severance Payments" shall mean those payments described in
Section 6.01 hereof.

          (X) "Stock Plans" shall mean the Company's 1996 Stock Incentive Plan,
1996 Broad-Based Employee Stock Plan and any other stock compensation plan
applicable to the Executive, or any similar successor plan or arrangement.

          (Y) "Subsidiary" shall mean any corporation, partnership or other
entity, at least a majority of the outstanding voting shares or controlling
interest of which is at the time directly or indirectly owned or controlled
(either alone or through Subsidiaries or together with Subsidiaries) by
Metromail or another Subsidiary.

                                      -31-
<PAGE>
 
          (Z) "Total Payments" shall mean those payments described in Section
6.02 hereof.

          (AA) "Window Period" shall mean the 90-day period commencing one year
after the date of a Change in Control.


                              METROMAIL CORPORATION

                              By /s/ Barton L. Faber
                                 -----------------------------------------------
                                 Barton L. Faber        
                                 Chairman


                                 /s/ Susan L. Henricks
                                 -----------------------------------------------
                                 Susan L. Henricks
                                 Executive


                                     -32-