<PAGE>

                                                                    EXHIBIT 10.4


"THIS WARRANT AND THE SHARES OF STOCK ISSUABLE UPON EXERCISE HEREOF HAVE NOT
BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933, AS AMENDED, AND MAY NOT BE
OFFERED, SOLD, TRANSFERRED, HYPOTHECATED OR OTHERWISE ASSIGNED EXCEPT PURSUANT
TO (1) A REGISTRATION STATEMENT WITH RESPECT TO SUCH SECURITIES WHICH IS
EFFECTIVE UNDER SUCH ACT OR (2) AN AVAILABLE EXEMPTION FROM REGISTRATION UNDER
SUCH ACT RELATING TO THE DISPOSITION OF SUCH SECURITIES."

                  WARRANT TO PURCHASE SHARES OF COMMON STOCK

     THIS CERTIFIES THAT, for value received, InfoSpace, Inc., a Delaware
corporation (the "Holder"), is entitled to subscribe for and purchase that
                  ------
number of shares as provided in Section 1 hereof (as adjusted pursuant to the
provisions hereof) of the Common Stock (as defined below) of USSearch.com Inc.,
a Delaware corporation (the "Company"), at a price per share of $.01 (as
                             -------
adjusted pursuant to the provisions hereof, the "Exercise Price"), subject to
                                                 --------------
the provisions and upon the terms and conditions hereinafter set forth in this
warrant ("Warrant").  A used herein, the term "Common Stock" shall mean the
          -------                              ------------
Company's presently authorized common stock, $.01 par value per share, and any
stock into or for which such Common Stock may hereafter be converted or
exchanged, and the term "Grant Date" shall mean October 1, 2000.
                         ----------

This Warrant is issued pursuant to that certain Contract Cancellation Settlement
and Release Agreement by and between the Company and the Holder (the
"Cancellation Agreement").
 ----------------------

     1.   Number of Shares; Term.  As of the Grant Date, the Holder shall be
          ----------------------
entitled to purchase up to an aggregate of 1,750,000 shares of Common Stock
pursuant to this Warrant.  This Warrant is exercisable with respect to such
shares, in whole or in part, at any time and from time to time from on or after
the Grant Date and prior to 5:00 p.m. Pacific Time on the tenth anniversary of
the Grant Date.

     2.   Method of Exercise and Payment; Issuance of New Warrant; Contingent
          -------------------------------------------------------------------
          Exercise.
          --------

          a.  Subject to Section 1 hereof, this Warrant may be exercised by the
     Holder hereof by the surrender of this Warrant (with the notice of exercise
     form attached hereto as Exhibit l-A duly executed) at the principal office
                             -----------
     of the Company and by the payment to the Company of cash or a certified
     check or a wire transfer in an amount equal to the then applicable Exercise
     Price multiplied by the number of shares of Common Stock then being
     purchased.  In the alternative, the Holder hereof may exercise its right to
     purchase some or all of the shares of Common Stock pursuant to this
     Warrant, on a net basis, such that, without the exchange of any funds, the
     Holder hereof receives that number of shares of Common Stock subscribed to
     pursuant to this Warrant less that number of shares of Common Stock having
     an aggregate fair market value (as defined below) at the time of exercise
     equal to the aggregate Exercise Price that would otherwise have been paid
     by the
<PAGE>

     Holder for the number of shares of Common Stock subscribed to under this
     Warrant. Fair market value, on a per-share basis, shall be deemed to be (i)
     the daily closing price (as defined below) per share on the date
     immediately preceding the date of exercise; and (ii) if the Common Stock is
     not publicly held, listed or traded, the fair value per share determined
     reasonably and in good faith by the Board of Directors of the Company. The
     closing price for each day shall be the last sale price or, in case no such
     sale takes place on such day, the average of the closing bid and asked
     prices, in either case as reported on the principal consolidated
     transaction reporting system with respect to securities listed on the
     principal national securities exchange on which the Common Stock is listed
     or admitted to trading; or, if not listed or admitted to trading on any
     national securities exchange, the last quoted price (or, if not so quoted,
     the average of the last quoted high bid and low asked prices) in the over-
     the-counter market, as reported by NASDAQ or such other system then in use;
     or, if on any such date no bids are quoted by any such organization, the
     average of the closing bid and asked prices as furnished by a professional
     market maker making a market in such security selected by the members of
     the Board of Directors of the Company.

          b  The Company agrees that the shares of Common Stock so purchased
     shall be deemed to be issued to the Holder hereof as the record owner of
     such shares as of the close of business on the date on which this Warrant
     shall have been surrendered and payment made for such shares as aforesaid.
     In the event of any exercise of the rights represented by this Warrant,
     certificates for the shares of Common Stock so purchased shall be delivered
     to the Holder hereof within 15 days thereafter and, unless this Warrant has
     been fully exercised or has expired pursuant to Section 1 hereof, a new
     Warrant representing the shares of Common Stock, if any, with respect to
     which this Warrant shall not then have been exercised, shall also be issued
     to the Holder hereof within such 15-day period.

     3.   Stock Fully Paid; Reservation of Share.  All shares of Common Stock
          --------------------------------------
issuable upon exercise of this Warrant shall, upon issuance, be validly issued,
fully paid and nonassessable, and free from all taxes, liens and charges with
respect to the issue thereof.  During the period within which this Warrant may
be exercised, the Company will at all times have duly authorized and reserved,
for the purpose of issuance upon exercise of this Warrant, a sufficient number
of shares of Common Stock.

     4.   Reclassification or Merger.  In case of any reclassification, stock
          --------------------------
split, stock dividend, change or conversion of securities of the class issuable
upon exercise of this Warrant (other than a change in par value, or from par
value to no par value, or from no par value to par value, or as a result of a
subdivision or combination), or in case of any merger of the Company with or
into another corporation or entity (other than a merger with another corporation
in which the Company is a continuing corporation and which does not result in
any reclassification or change of outstanding securities issuable upon exercise
of this Warrant), or in case of any sale of all or substantially all of the
assets of the Company, the Company, or such successor or purchasing corporation
or entity, as the case may be, shall execute a new Warrant (in form and
<PAGE>

substance satisfactory to the Holder of this Warrant) providing that the Holder
of this Warrant shall have the right to exercise such new Warrant and upon such
exercise to receive, in lieu of each share of Common Stock, the kind and amount
of shares of stock, other securities, money and property receivable upon such
reclassification, change or merger by a holder of one share of Common Stock.
Such new Warrant shall provide for adjustments that shall be as nearly
equivalent as may be practicable to the adjustments provided for in this Section
4.  The provisions of this Section 4(e) shall similarly apply to successive
reclassifications, changes, mergers and transfers.

     5.   No Impairment.  The Company will not, by amendment of its certificate
          -------------
of incorporation or through any reorganization, recapitalization, transfer of
assets, consolidation, merger, dissolution, issuance or sale of securities or
any other voluntary action, avoid or seek to avoid the observance or performance
of any of the terms to be observed or performed hereunder by the Company, and
will take all such actions as may be necessary or appropriate in order to
protect the rights of the Holder of this Warrant against impairment.

     6.   Notices of Record Date. In the event of any taking by the Company of a
          ----------------------
record of its shareholders for the purpose of determining shareholders who are
entitled to receive payment of any dividend or other distribution, any right to
subscribe for, purchase or otherwise acquire any share of any class or any other
securities or property, or to receive any other right, or for the purpose of
determining shareholders who are entitled to vote in connection with any
proposed merger or consolidation of the Company with or into any other
corporation, or any proposed sale, lease or conveyance of all or substantially
all of the assets of the Company, or any proposed liquidation, dissolution or
winding up of the Company, then, in connection with each such event, the Company
shall mail to the Holder of this Warrant at least fifteen (15) days prior
written notice of the date on which any such record is to be taken for the
purpose of such dividend, distribution, right(s) or vote of the shareholders.
Each such written notice shall specify the amount and character of any such
dividend, distribution or right(s), and shall set forth, in reasonable detail,
the matter requiring any such vote of the shareholders.

     7.   Fractional Shares.  No fractional shares of Common Stock will be
          -----------------
issued in connection with any exercise hereunder, but in lieu of such fractional
shares the Company shall make a cash payment therefor based upon the per share
fair market value of the Common Stock on the date of exercise.

     8.   Compliance with Securities Act: Disposition of Warrant or Shares of
          -------------------------------------------------------------------
Common Stock.
------------

          a.  Compliance with Securities Act.  The Holder of this Warrant, by
              ------------------------------
     acceptance hereof, agrees that this Warrant and the shares of Common Stock
     to be issued upon exercise hereof are being acquired for investment and
     that such Holder will not offer, sell or otherwise dispose of this Warrant
     or any shares of Common Stock to be issued upon exercise hereof except
     under circumstances which will not result in a violation of the Securities
     Act. This Warrant and all shares of Common Stock issued
<PAGE>

     upon exercise of this Warrant (unless registered under the Securities Act)
     shall be stamped or imprinted with a legend in substantially the following
     form:

"THE SECURITIES REPRESENTED HEREBY HAVE NOT BEEN REGISTERED UNDER THE SECURITIES
ACT OF 1933, AS AMENDED, AND MAY NOT BE OFFERED, SOLD, TRANSFERRED, HYPOTHECATED
OR OTHERWISE ASSIGNED EXCEPT PURSUANT TO (1) A REGISTRATION STATEMENT WITH
RESPECT TO SUCH SECURITIES WHICH IS EFFECTIVE UNDER SUCH ACT OR (2) AN AVAILABLE
EXEMPTION FROM REGISTRATION UNDER SUCH ACT RELATING TO THE DISPOSITION OF SUCH
SECURITIES."

          b.  Disposition of Warrant and Shares of Common Stock Issue Upon
              ------------------------------------------------------------
     Exercise of Warrant.  With respect to any offer, sale or other disposition
     -------------------
     of this Warrant or any shares of Common Stock issued upon exercise of this
     Warrant prior to registration thereof, the Holder hereof and each
     subsequent holder of this Warrant agrees to give written notice to the
     Company prior thereto, describing briefly the manner thereof, together with
     a written opinion of such holder's counsel in form acceptable to the
     Company's counsel, if reasonably requested by the Company, to the effect
     that such offer, sale or other disposition may be effected without
     registration or qualification (under the Securities Act then in effect or
     any federal or state law then in effect) of this Warrant or such shares of
     Common Stock and indicating whether or not under the Securities Act
     certificates for this Warrant or such shares of Common Stock to be sold or
     otherwise disposed of require any restrictive legend as to applicable
     restrictions on transferability in order to insure compliance with the
     Securities Act.  Each certificate representing this Warrant or the shares
     of Common Stock thus transferred (except a transfer pursuant to Rule 144)
     shall bear a legend as to the applicable restrictions on transferability in
     order to insure compliance with the Securities Act unless, in the aforesaid
     opinion of counsel for the holder, such legend is not required in order to
     ensure compliance with the Securities Act.  The Company may issue stop
     transfer instructions to its transfer agent in connection with the
     foregoing restrictions.

     9.   Appraisal Rights.  In the event of any dispute between the Holder of
          ----------------
this Warrant or the shares of Common Stock issued upon the exercise of this
Warrant and the Company regarding the determination of fair market value, the
Company and the Holder shall first use their best efforts to resolve such
dispute among themselves or to agree upon the selection of an independent, non-
affiliated consulting firm or investment banking firm of national standing (an
"Independent Appraiser") to make a final and binding determination of fair
 ---------------------
market value. If the parties are unable to resolve the dispute or to agree upon
an Independent Appraiser within thirty (30) calendar days after the commencement
of efforts to resolve the dispute, the Holder and the Company each shall select
an Independent Appraiser within thirty (30) days after the conclusion of such
initial thirty (30) day period. Within ten (10) days after such selection, such
Independent Appraisers shall select a third non-affiliated consulting firm or
investment banking firm. of national standing (the "Second Appraiser") to make a
                                                    ----------------
final and binding determination of fair market value.  The Company and the
Holder shall each be
<PAGE>

responsible for the fees and expenses of the Independent Appraiser selected by
such party. The determination of the Independent Appraiser selected by agreement
of the parties or the Second Appraiser selected as provided above (as the case
may be) shall be final and binding on the Company and the Holder, and the
expenses of such agreed upon Independent Appraiser or Second Appraiser (as the
case may be) shall be borne one-half by the Company and one-half by the Holder.

     10.  Mergers.  The Company shall provide the Holder of this Warrant with
          -------
at least thirty (30) days' notice or such greater amount of notice as Delaware
law requires to be given to shareholders having the right to vote at a meeting
on any transaction described hereafter, of the terms and conditions of any
proposed transaction, in which the Company would (i) sell, lease, exchange,
convey or otherwise dispose of all or substantially all of its property or
business, (ii) merge into or consolidate with any other corporation (other than
a wholly owned subsidiary of the Company), or (iii) sell, lease, exchange,
convey or otherwise dispose of a material and significant asset or group of
assets of the Company or of any subsidiary of the Company, or effect any
transaction (including a merger or other reorganization) or series of related
transactions, in which more than fifty percent (50%) of the voting power of the
Company is disposed of.

     11.  Representations and Warranties.  This Warrant is issued and delivered
          ------------------------------
on the basis of the following:

          a.  This Warrant has been duly authorized, executed and delivered by
     the Company and constitutes the valid and binding obligation of the
     Company, enforceable in accordance with its terms.

          b.  The shares of and Common Stock issuable upon exercise of this
     Warrant have been duly authorized and reserved for issuance by the Company
     and, when issued in accordance with the terms hereof, will be validly
     issued, fully paid and nonassessable.

     12.  Modification and Waiver.  This Warrant and any provision hereof may be
          -----------------------
changed, waived, discharged or terminated only by an instrument in writing
signed by the party against which enforcement of the same is sought.

     13.  Notices.  Any notice, request or odor document required or permitted
          -------
to be given or delivered to the Holder hereof or the Company shall be in writing
and shall delivered or sent to each such Holder at its address as shown on the
books of the Company or to the Company at its principal executive office and
shall be deemed received (i) if personally delivered or sent by electronic
facsimile transmission, upon actual receipt, or (ii) if sent by reputable
overnight courier service, twenty-four hours after deposit with such courier
service, or (iii) if sent by certified mail (postage prepaid), return receipt
requested, forty-eight hours after deposit in the mail.

     14.  Binding Effect on Successors.  This Warrant shall be binding upon any
          ----------------------------
<PAGE>

corporation succeeding the Company by merger, consolidation or acquisition of
all or substantially all of the Company's assets. All of the obligations of the
Company relating to the shares of Common Stock issued upon exercise of this
Warrant shall survive the exercise and termination of this Warrant. All of the
covenants and agreements of the Company shall inure to the benefit of the
successors and assigns of the Holder hereof.  The Company will, at the time of
the exercise of this Warrant, in whole or in part, upon request of the Holder
hereof, acknowledge in writing its continuing obligation to the Holder hereof in
respect of any rights to which the Holder hereof shall continue to be entitled
after such exercise in accordance with this Warrant; provided that the failure
of the Holder hereof to make any such request shall not affect the continuing
obligation of the Company to the Holder hereof in respect of such rights.

     15.  Lost Warrants or Stock Certificates.  The Company covenants to the
          -----------------------------------
Holder hereof that upon receipt of evidence reasonable satisfactory to the
Company of the loss, theft, destruction, or mutilation of this Warrant or any
stock certificate issued upon exercise hereof and, in the case of any such loss,
theft or destruction, upon receipt of an indemnity reasonably. satisfactory to
the Company, or in the case of any such mutilation upon surrender and
cancellation of such Warrant or stock certificate, the Company shall make and
deliver a new Warrant or stock certificate, or like tenor, in lieu of the lost,
stolen, destroy6d or mutilated Warrant or stock certificate.

     16.  Descriptive Headings.  The descriptive headings of the several
          --------------------
paragraphs of this Warrant are inserted for convenience only and do not
constitute a part of this Warrant.

     17.  Governing Law.  This Warrant shall be construed and enforced in
          -------------
accordance with and governed by the laws of the State of Delaware (without
giving effect to its conflicts of laws provisions).  Each party also waives
trial by jury in any action relating to this Warrant.
<PAGE>

     IN WITNESS WHEREOF, the Company has caused this Warrant to be executed by
its officers thereunto duly authorized.

Date: September 29, 2000


                                                  USSEARCH.com, INC.


                                                  By: /s/ Karol Pollock
                                                     --------------------------
                                                  Name:  Karol Pollock
                                                       ------------------------
                                                  Its: General Counsel
                                                      -------------------------
<PAGE>

                                  EXHIBIT A-1

                            NOTICE OF EXERCISE To:

To:


          1.  The undersigned hereby:
_____________________________ elects to purchase _______________________ shares
of Common Stock of the Company pursuant to the terms of the attached Warrant,
and tenders herewith payment of the purchase price of such shares in full in the
form of _______________________________________________________________________;
or ______________ elects to exercise its net issuance rights pursuant to Section
2(c) of the attached Warrant with respect to shares of Common Stock.

          2.  Please issue a certificate or certificates representing said
_______________shares in the name of the undersigned or in such other name or
names as are specified below:



________________________________________________________________________________
____________________________________
             (Name)


________________________________________________________________________________
____________________________________
            (Address)

          3.  Please issue a new Warrant for the unexercised portion of the
attached Warrant in the name of the undersigned or in such other name as
specified below.


Date: _______________________                ___________________________________
                                             (Name)


                                             By:________________________________
                                             Name:______________________________
                                             Title:_____________________________
                                             Address:___________________________