<PAGE>

                                                                   Exhibit 10.36

NEITHER THIS WARRANT NOR THE SHARES OF CLASS A COMMON STOCK ISSUABLE UPON
EXERCISE OF THIS WARRANT HAVE BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933,
AND NEITHER THIS WARRANT NOR SUCH SHARES MAY BE SOLD, ENCUMBERED OR OTHERWISE
TRANSFERRED EXCEPT PURSUANT TO AN EFFECTIVE REGISTRATION STATEMENT UNDER SUCH
ACT OR AN EXEMPTION FROM SUCH REGISTRATION REQUIREMENT, AND, IF AN EXEMPTION
SHALL BE APPLICABLE, THE HOLDER SHALL HAVE DELIVERED AN OPINION OF COUNSEL
REASONABLY ACCEPTABLE TO THE COMPANY THAT SUCH REGISTRATION IS NOT REQUIRED.


              Void after 5:00 p.m. Eastern Time, on May 11,2004.


                   WARRANT TO PURCHASE CLASS A COMMON STOCK
                                      OF
                              VIDEO UPDATE, INC.

                               1,000,000 Shares


     FOR VALUE RECEIVED, VIDEO UPDATE, INC. (the "Company"), a Delaware
corporation, hereby certifies that Ingram Entertainment Inc. or its permitted
assigns, is entitled to purchase from the Company, at any time or from time to
time (subject, however, to the restrictions set forth herein) commencing May 11,
1999, and prior to 5:00 p.m., Eastern Time, on May 11, 2004, a total of One
Million (1,000,000) fully paid and nonassessable shares of the Class A Common
Stock, par value $.01 per share ("Common Stock"), of the Company for an
aggregate purchase price of Eight Hundred Ten Thousand and 00/100 Dollars
($810,000.00) (computed on the basis of $.81 per share).

     Hereinafter, (i) said Common Stock, together with any other equity
     securities which may be issued by the Company with respect thereto or in
     substitution therefor, is referred to as the "Common Stock," (ii) the
     shares of the Common Stock purchasable hereunder are referred to as the
     "Warrant Shares," (iii) the aggregate purchase price payable hereunder for
     the Warrant Shares is referred to as the "Aggregate Warrant Price," (iv)
     the price payable hereunder for each of the Warrant Shares is referred to
     as the "Per Share Warrant Price," (v) this Warrant, and all warrants
     hereafter issued in exchange or substitution for this Warrant are referred
     to as the "Warrant" and (vi) the holder of this Warrant, together with any
     permitted transferee or assignee, is referred to as the "Holder."  The Per
     Share Warrant Price is subject to adjustment as hereinafter provided; in
     the event of any such adjustment, the number of Warrant
<PAGE>

     Shares shall be adjusted by dividing the Aggregate Warrant Price by the Per
     Share Warrant Price in effect immediately after such adjustment.

     1.   Exercise of Warrant.  This Warrant may be exercised, in whole at any
          -------------------
time or in part from time to time, commencing May 11, 1999 and prior to 5:00
P.M., Eastern Time then current, on May 11, 2004, by the Holder of this Warrant
by the surrender of this Warrant (with the subscription form at the end hereof
duly executed) at the address set forth in Subsection 9(a) hereof, together with
proper payment of the Aggregate Warrant Price, or the proportionate part thereof
if this Warrant is exercised in part.

     Payment for Warrant Shares shall be made by certified or official bank
check payable to the order of the Company, by wire transfer or, at the option of
the Holder, in whole or in part by forgiveness of indebtedness (including
principal, interest, fees or late charges) of the Company to the Holder,
including indebtedness evidenced by one or more promissory notes. If this
Warrant is transferred or exercised in part, the Holder is entitled to receive a
new Warrant covering the number of Warrant Shares in respect of which this
Warrant has not been transferred or exercised and setting forth the
proportionate part of the Aggregate Warrant Price applicable to such Warrant
Shares. Upon such surrender of this Warrant, the Company will issue a
certificate or certificates in the name of the Holder, or as such Holder may
direct, for the number of shares of the Common Stock to which the Holder shall
be entitled, plus in lieu of any fractional shares to which such Holder would be
otherwise entitled, cash in an amount equal to the Per Share Warrant Price times
the fraction.

     2.   Reservation of Warrant Shares.  The Company agrees that, prior to the
          -----------------------------
expiration of this Warrant, the Company will at all times have authorized and in
reserve, and will keep available, solely for issuance and delivery upon the
exercise of this Warrant, the shares of the Common Stock as from time to time
shall be receivable upon the exercise of this Warrant.

     3.   Adjustments.
          -----------

          (a)  If, at any time or from time to time after the date of this
Warrant, the Company shall distribute to the holders of the Common Stock (i)
securities, other than shares of the Common Stock, or (ii) property, other than
cash, without payment therefor, with respect to the Common Stock, then, and in
each such case, the Holder, upon the exercise of this Warrant, shall be entitled
to receive the securities and properties which the Holder would hold on the date
of such exercise if, on the date of this Warrant, the Holder had been the holder
of record of the number of shares of the Common Stock subscribed for upon such
exercise and, during the period from the date of this Warrant to and including
the date of such exercise, had retained such shares and the securities and
properties receivable by the Holder during such period.  Notice of each such
distribution shall be forthwith mailed to the Holder.

          (b)  In case the Company shall hereafter (i) pay a dividend or make a
distribution on its capital stock in shares of Common Stock, (ii) subdivide its
outstanding

                                      -2-
<PAGE>

shares of Common Stock into a greater number of shares, (iii) combine its
outstanding shares of Common Stock into a smaller number of shares or (iv) issue
by reclassification of its Common Stock any shares of capital stock of the
Company, the Per Share Warrant Price (and number of Warrant Shares) in effect
immediately prior to such action shall be adjusted so that if the Holder
surrendered this Warrant for exercise immediately thereafter the Holder would be
entitled to receive the number of shares of Common Stock or other capital stock
of the Company which he would have owned immediately following such action had
such Warrant been exercised immediately prior thereto. An adjustment made
pursuant to this subsection (b) shall become effective immediately after the
record date in the case of a dividend or distribution and shall become effective
immediately after the effective date in the case of a subdivision, combination
or reclassification. If, as a result of an adjustment made pursuant to this
subsection (b), the Holder of this Warrant shall become entitled to receive
shares of two or more classes of capital stock or shares of Common Stock and
other capital stock of the Company, the Board of Directors (whose determination
shall be made reasonably and in good faith and shall be described in a written
notice to the Holder of this Warrant promptly after such adjustment) shall
determine the allocation of the adjusted Per Share Warrant Price between or
among shares of such classes of capital stock or shares of Common Stock and
other capital stock, based upon the fair market value of such Common Stock and
other capital stock.

          (c)  In case of any consolidation or merger to which the Company is a
party other than a merger or consolidation in which the Company is the
continuing corporation, or in case of any sale or conveyance to another entity
or entities of the property of the Company as an entirety or substantially as an
entirety, or in the case of any statutory exchange of securities with another
corporation (including any exchange effected in connection with a merger of a
third corporation into the Company), the Holder shall have the right thereafter
to convert this Warrant into the kind and amount of securities, cash or other
property which he would have owned or have been entitled to receive immediately
after such consolidation, merger, statutory exchange, sale or conveyance had
such Warrant been converted immediately prior to the effective date of such
consolidation, merger, statutory exchange, sale or conveyance and in any such
case, if necessary, appropriate adjustment shall be made in the application of
the provisions set forth in this Section 3 with respect to the rights and
interests thereafter of the Holder to the end that the provisions set forth in
this Section 3 shall thereafter correspondingly be made applicable, as nearly as
may reasonably be, in relation to any shares of stock or other securities or
property thereafter deliverable on the conversion of this Warrant.  The above
provisions of this subsection (c) shall similarly apply to successive
consolidations, mergers, statutory exchanges, sales or conveyances. Notice of
any such consolidation, merger, statutory exchange, sale or conveyance and of
said provisions so proposed to be made, or of any liquidation or dissolution of
the Company, shall be mailed to the Holder not less than ten (10) business days
prior to such event. A sale of all or substantially all of the assets of the
Company for a consideration consisting primarily of securities shall be deemed a
consolidation or merger for the foregoing purposes.

          (d)  Whenever the Per Share Warrant Price and the number of Warrant
Shares is adjusted as provided in this Section 3 and upon any modification of
the rights of

                                      -3-
<PAGE>

the Holder of this Warrant in accordance with this Section 3, the Company shall
promptly prepare a certificate of an officer of the Company, setting forth the
Per Share Warrant Price and the number of Warrant Shares after such adjustment
or modification, a brief statement of the facts requiring such adjustment or
modification and the manner of computing the same and cause a copy of such
certificate to be mailed to the Holder.

          (e)  If the Board of Directors of the Company shall declare any
dividend or other distribution in cash with respect to the Common Stock, other
than out of earned surplus, the Company shall mail notice thereof to the Holder
not less than five (5) days prior to the record date fixed for determining
shareholders entitled to participate in such dividend or other distribution and
shall pay or distribute to the Holder of this Warrant, upon the exercise hereof,
in addition to the Warrant Shares purchased upon such exercise, such dividend or
distribution which would have been paid to the Holder if the Holder had been the
owner of record of such Warrant Shares immediately prior to the record date for
such dividend or distribution.

    (f)   Except in connection with the conversion or exercise of any
outstanding Options (as defined below) or Convertible Securities (as defined
below) of the Company or Moovies, Inc. (as such Options and Convertible
Securities are in effect on the date hereof) or with respect to any Option
granted under an option plan adopted by the Board of Directors of the Company
for the benefit of employees, independent contractors and similar persons (an
"Approved Option Plan"), in the event the Company shall, at any time or from
time to time after the date hereof, issue, sell, distribute or otherwise grant
in any manner (including by assumption) any rights to subscribe for or to
purchase, or any warrants or options for the purchase of, or any stock or
securities convertible into or exchangeable for Common Stock (any such rights,
warrants or options being herein called "Options" and any such convertible or
                                         -------
exchangeable stock or securities being herein called "Convertible Securities")
                                                      ----------------------
or any Convertible Securities (other than upon exercise of any Option), whether
or not such Options or the rights to convert or exchange such Convertible
Securities are immediately exercisable, and the price per share at which Common
Stock is issuable upon the exercise of such Options or upon the conversion or
exchange of such Convertible Securities (determined by dividing (i) the
aggregate amount if any, received or receivable by the Company as consideration
for the issuance, sale, distribution or granting of such Options or any such
Convertible Security, plus the minimum aggregate amounts of additional
consideration, if any, payable to the Company upon the exercise of all such
Options or upon conversion or exchange of all such Convertible Securities, plus,
in the case of Options to acquire Convertible Securities, the minimum aggregate
amount of additional consideration, if any, payable upon the conversion or
exchange of all such Convertible Securities, by (ii) the total maximum number of
shares of Common Stock issuable upon the exercise of all such Options or upon
the conversion or exchange of all such Convertible Securities or upon the
conversion or exchange of all Convertible Securities issuable upon the exercise
of all such Options) shall be less than the Market Price (as defined below) per
share of Common Stock on the record date for the issuance, sale, distribution or
granting of such Options (any such event being herein called a "Distribution")
                                                                ------------
then, effective upon such Distribution, the Per Share Warrant Price shall be
reduced to the price (calculated to the nearest 1/1,000 of one cent) determined
by multiplying such Per Share Warrant Price in effect immediately

                                      -4-
<PAGE>

prior to such Distribution by a fraction, the numerator of which shall be the
sum of (i) the number of shares of Common Stock outstanding (exclusive of any
treasury shares) immediately prior to such Distribution multiplied by the Market
Price per share of Common Stock on the date of such Distribution plus (ii) the
consideration, if any, received by the Company upon such Distribution, and the
denominator of which shall be the product of (A) the total number of shares of
Common Stock outstanding (exclusive of any treasury shares) immediately after
such Distribution multiplied by (B) the Market Price per share of Common Stock
on the record date for such Distribution. For purposes of the foregoing, the
total maximum number of shares of Common Stock issuable upon exercise of all
such Options or upon conversion or exchange of all such Convertible Securities
or upon the conversion or exchange of the total maximum amount of the
Convertible Securities issuable upon the exercise of all such Options shall be
deemed to have been issued as of the date of such Distribution and thereafter
shall be deemed to be outstanding and the Company shall be deemed to have
received as consideration therefor such price per share, determined as provided
above. No additional adjustment of Per Share Warrant Price shall be made upon
the actual exercise of such Options or upon conversion or exchange of the
Convertible Securities or upon the conversion or exchange of the Convertible
Securities issuable upon the exercise of such Options. "Market Price" means,
with respect to a share of Common Stock on any business day:

                    (a)  If the Common Stock is (i) listed on a domestic
          securities exchange, (ii) quoted on NASDAQ or (iii) traded in the
          domestic over-the-counter market, which trades are reported by the
          National Quotation Bureau, Incorporated ((i) - (iii) defined herein as
          "Publicly Traded") at the time of determination, the average of the
          closing prices on such day of the Common Stock on all domestic
          securities exchanges on which the Common Stock is then listed or, if
          there have been no sales on any such exchange on such day, the average
          of the highest bid and lowest asked prices on all such exchanges at
          the end of such day, or if on any such day the Common Stock is not so
          listed, the average of the representative bid and asked prices quoted
          on the NASDAQ System as of 4:00 P.M., New York time, on such day, or
          if on any day such security is not quoted on the NADSAQ System, the
          average of the highest bid and lowest asked prices on such day in the
          domestic over-the-counter market as reported by the National Quotation
          Bureau, Incorporated, or any similar successor organization, in each
          such case averaged over a period of thirty (30) days consisting of the
          day as of which Market Price is being determined and the twenty-nine
          (29) consecutive business days prior to such day (provided that, if
                                                            --------
          Market Price is being determined as of the date of a bona fide public
          offering, Market Price as of such date shall be the offering price of
          the Common Stock subject to such public offering; or

                    (b)  if the Common Stock is not Publicly Traded at the time
          of determination, the Common Stock Per Share Market Value.  "Common
          Stock Per Share Market Value" means the price per share of the Common
          Stock obtained by dividing (A) the Market Value by (B) the number of
          shares of Common Stock outstanding (on a Fully-Diluted Basis) at the
          time of

                                      -5-
<PAGE>

          determination. "Market Value" means the highest price that would be
                          ------------
          paid for the entire common equity of the Company on a going-concern
          basis in an arm's-length transaction between a willing buyer and a
          willing seller (neither acting under compulsion), using valuation
          techniques then prevailing in the securities industry (but without
          giving effect to any discount in respect of a minority interest), and
          assuming full disclosure and understanding of all relevant information
          and a reasonable period of time for effectuating such sale. For the
          purposes of determining the Market Value, (a) the exercise price of
          options or warrants to acquire Common Stock which are deemed to have
          been exercised for the purpose of determining the number of shares of
          Common Stock outstanding on a Fully-Diluted Basis (as defined below),
          shall be deemed to have been received by the Company, (b)(i) the
          liquidation preference or indebtedness, as the case may be,
          represented by securities which are deemed exercised for or converted
          into Common Stock for the purpose of determining the number of shares
          of Common Stock outstanding on a Fully-Diluted Basis and (ii) any
          contractual limitation in respect of the shares of Common Stock
          relating to voting rights, shall be deemed to have been eliminated or
          cancelled and (c) full effect shall be given to any discount that may
          arise as the result of the fact that the shares of
          Common Stock are not Publicly Traded. "Fully-Diluted Basis" means, as
                                                 -------------------
          applied to the calculation of the total number of shares of Common
          Stock outstanding at any time, after giving effect to (a) all shares
          of Common Stock outstanding at the time of determination, and (b) all
          shares of Common Stock issuable upon the exercise of any Convertible
          Security (including this Warrant) or similar right to purchase Common
          Stock outstanding at the time of determination and then so convertible
          or exchangeable at a conversion or exchange price equal to or less
          than the Market Price per share of Common Stock at such time.

     (g)  If at any time the Company shall (except as hereinafter provided)
issue or sell any Additional Shares (as defined below) for consideration in an
amount per Additonal Share less than the Market Price, then the Warrant Shares
shall be adjusted to equal the product obtained by multiplying the number of
Warrant Shares immediately prior to such issue or sale by a fraction (A) the
numerator of which shall be the number of shares of Common Stock outstanding
immediately after such issue or sale (on a Fully-Diluted Basis), and (B) the
denominator of which shall be the sum of (1) the number of shares of Common
Stock outstanding immediately prior to such issue or sale (on a Fully-Diluted
Basis), and (2) the aggregate consideration received from the issuance or sale
of the Additional Shares divided by the Market Price. For the purposes of this
subsection (g), the date as of which the Market Price per share of Common Stock
shall be computed shall be the earlier of (a) the first business day on which
the Company shall be able to determine the Market Price per share of Common
Stock pursuant to the the terms of a firm contract for the issuance of such
Additional Shares or (b) the date of actual issuance of such Additional Shares.
"Additional Shares" means any shares of Common Stock issued after the date
hereof except (i) Common Stock issued upon the exercise of any Warrant, (ii)
except as provided in clause (iii) below, Common Stock issued upon conversion or
exercise of any outstanding Options or Convertible Securities of the Company or
Moovies, Inc. (as such Options and Convertible

                                      -6-
<PAGE>

Securities are in effect on the date hereof); (iii) Common Stock issued upon
conversion or exercise of any Option or other rights granted under Approved
Option Plans or a rights plan; or (iv) Common Stock issued pursuant to or upon
stock splits, combinations or dividends or other transactions described in the
subsections to this Section 3 (after giving effect to any adjustments required
to be made by such subsections).

     (h)  No adjustment shall be made in connection with the issuance of shares
of Common Stock or other securities in a bona fide public offering pursuant to a
firm commitment underwriting by a firm which is member of the National
Association of Securities Dealers, Inc.

     4.   Fully Paid Stock; Taxes.  The Company agrees that the shares of the
          -----------------------
Common Stock represented by each and every certificate for Warrant Shares
delivered on the exercise of this Warrant shall, at the time of such delivery,
be validly issued and outstanding, fully paid and non-assessable, and not
subject to pre-emptive rights, and the Company will take all such actions as may
be necessary to assure that the par value or stated value, if any, per share of
the Common Stock is at all times equal to or less than the then Per Share
Warrant Price. The Company further covenants and agrees that it will pay, when
due and payable, any and all federal and state stamp, original issue or similar
taxes that may be payable in respect of the issue of any Warrant Share or
certificate therefor.

     5.   Transfer.
          --------

          (a)  Securities Laws.  Neither this Warrant nor the Warrant Shares
               ---------------
issuable upon the exercise hereof have been registered under the Securities Act
of 1933, as amended (the "Securities Act") or under any state securities laws
and unless so registered may not be transferred, sold, pledged, hypothecated or
otherwise disposed of unless an exemption from such registration is available.
In the event Holder desires to transfer this Warrant or any of the Warrant
Shares issued, the Holder must give the Company prior written notice of such
proposed transfer including the name and address of the proposed transferee.
Such transfer may be made only either (i) upon issuance by the Securities and
Exchange Commission (the "Commission") of a ruling, interpretation, opinion or
"no action letter" based upon facts presented to said Commission, or (ii) upon
receipt by the Company of an opinion of counsel to the Holder, reasonably
acceptable to the Company, in either case to the effect that the proposed
transfer will not violate the provisions of the Securities Act, or the rules and
regulations promulgated under such act, or in the case of clause (ii) above, to
the effect that the Warrant or Warrant Shares to be sold or transferred has been
registered under the Securities Act, and that there is in effect a current
prospectus meeting the requirements of Subsection 10(a) of the Securities Act,
which is being or will be delivered to the purchaser or transferee at or prior
to the time of delivery of the certificates evidencing the Warrant or Warrant
Shares to be sold or transferred.

          (b)  Lock-Up Agreements with Underwriters.  In the event of a public
               ------------------------------------
offering of the Company's securities, the Holder agrees to enter into an
agreement with the underwriter or underwriter's representative for such offering
restricting the sale, transfer or other disposition of this Warrant or the
Warrant Shares for a period of 90 days after the

                                      -7-
<PAGE>

offering to the extent that such agreement is required to be executed by the
underwriter or the underwriter's representative.

          (c) Conditions to Transfer.  Prior to any such proposed transfer, and
              ----------------------
as a condition thereto, if such transfer is not made pursuant to an effective
registration statement under the Securities Act, the Holder will, if requested
by the Company, deliver to the Company (i) an agreement by the proposed
transferee to the impression of the restrictive investment legend set forth
herein on the certificate or certificates representing the securities acquired
by such transferee, (ii) an agreement by such transferee that the Company may
place a "stop transfer order" with its transfer agent or registrar, and (iii) an
agreement by the transferee to indemnify the Company to the same extent as set
forth in the next succeeding paragraph.

          (d) Indemnity.  The Holder acknowledges that the Holder understands
              ---------
the meaning and legal consequences of this Section 5, and the Holder hereby
agrees to indemnify and hold harmless the Company, its representatives and each
officer and director thereof from and against any and all loss, damage or
liability (including all reasonable attorneys' fees and costs incurred in
enforcing this indemnity provision) due to or arising out of (a) the inaccuracy
of any representation or the breach of any warranty of the Holder contained in,
or any other breach of, this Warrant, (b) any transfer of any of the Warrant or
the Warrant Shares in violation of the Securities Act or the rules and
regulations promulgated under such act, (c) any transfer of the Warrant or any
of the Warrant Shares not in accordance with this Warrant or (d) any untrue
statement or omission to state any material fact in connection with the
investment representations or with respect to the facts and representations
supplied by the Holder to counsel to the Company upon which its opinion as to a
proposed transfer shall have been based.

          (e) Transfer.  Except as restricted hereby, this Warrant and the
              --------
Warrant Shares issued may be transferred by the Holder in whole or in part at
any time or from time to time; provided, however, that neither this Warrant nor
the Warrant Shares may be transferred to any person or entity that competes with
the business of the Company, as set forth on Schedule I hereto.  Upon surrender
                                             ----------
of this Warrant to the Company or at the office of its stock transfer agent, if
any, with assignment documentation duly executed and funds sufficient to pay any
transfer tax, and upon compliance with the foregoing provisions, the Company
shall, without charge, execute and deliver a new Warrant in the name of the
assignee named in such instrument of assignment, and this Warrant shall promptly
be cancelled.  Any assignment, transfer, pledge, hypothecation or other
disposition of this Warrant attempted contrary to the provisions of this
Warrant, or any levy of execution, attachment or other process attempted upon
the Warrant, shall be null and void and without effect.

          (f) Legend and Stop Transfer Orders.  Unless the Warrant Shares have
              -------------------------------
been registered under the Securities Act, upon exercise of any part of the
Warrant and the issuance of any of the shares of Warrant Shares, the Company
shall instruct its transfer agent to enter stop transfer orders with respect to
such shares, and all certificates representing

                                      -8-
<PAGE>

Warrant Shares shall bear on the face thereof substantially the following
legend, insofar as is consistent with Delaware law:

          "THE SHARES REPRESENTED BY THIS CERTIFICATE HAVE NOT BEEN
          REGISTERED UNDER THE SECURITIES ACT OF 1933 OR UNDER ANY
          STATE LAW AND, EXCEPT PURSUANT TO AN EFFECTIVE REGISTRATION
          STATEMENT UNDER SUCH ACT AND OTHER LAWS, MAY NOT BE OFFERED,
          SOLD, TRANSFERRED, OR OTHERWISE DISPOSED OF WITHOUT AN
          OPINION OF COUNSEL, REASONABLY SATISFACTORY TO THE COMPANY,
          THAT SUCH DISPOSITION MAY BE MADE WITHOUT SUCH
          REGISTRATION."

The foregoing legend shall be removed from the certificates representing any
Warrant Shares at the request of the Holder thereof at such time as they become
eligible for resale pursuant to Rule 144(k) of the Securities Act.

     6.  Registration Rights.  The Company shall register any Warrant or Warrant
         -------------------
Shares, to permit the sale or other disposition thereof in accordance with the
registration requirements of the Securities Act or any state securities laws or
regulations in accordance with the Registration Rights Agreement annexed as
Exhibit 1.
---------

     7.   Redemption.
          ----------

     (a)  If, at any time following the date hereof, the average closing bid
price for any twenty (20) consecutive business days of the Common Stock as
reported by Nasdaq or (ii) alternatively, the last reported sale price, for any
twenty (20) consecutive business days on any other primary exchange on which the
Common Stock is instead traded, is at least $6.00 (the "Target Price"), then the
Company, at its option, may redeem the Warrant (or any unexercised portion
thereof) at a redemption price of $0.05 per Warrant Share (the "Redemption
Price"). The date fixed for redemption of the Warrant is referred to herein as
the "Redemption Date".

     (b)  If the conditions set forth above are met, and the Company desires to
exercise its right to redeem the Warrant as described above, it shall mail a
notice of redemption to the Holder, certified or registered mail, postage
prepaid, not later than the tenth day before the date fixed for redemption, at
the last address for the Holder as shall appear on the records of the Company.
Any notice mailed in the manner provided herein shall be conclusively presumed
to have been duly given whether or not the Holder receives such notice.

     (c)  The notice of redemption shall specify (i) the Redemption Price, (ii)
the Redemption Date, (iii) the place where the Warrant shall be delivered and
the Redemption Price paid, (iv) that the right to exercise the Warrant shall
terminate at 5:00 P.M. (Eastern time) on the business day immediately preceding
the Redemption Date.  No failure to mail

                                      -9-
<PAGE>

such notice nor any defect therein or in the mailing thereof shall affect the
validity of the proceedings for such redemption except as to a Holder (a) to
whom notice was not mailed or (b) whose notice was defective.

     (d) Any right to exercise a Warrant (or any unexercised portion thereof)
shall terminate at 5:00 P.M. (Eastern time) on the business day immediately
preceding the Redemption Date.  On and after the Redemption Date, a Holder shall
have no further rights except to receive, upon surrender of the Warrant, the
Redemption Price.

     (e) From and after the Redemption Date, the Company shall, at the place
specified in the notice of redemption, upon presentation and surrender to the
Company by or on behalf of the Holder thereof of the Warrant (or any unexercised
portion thereof) to be redeemed, deliver or cause to be delivered to or upon the
written order of such Holder a sum in cash equal to the Redemption Price of each
such Warrant or portion thereof.  From and after the Redemption Date and upon
the deposit or setting aside by the Company of a sum sufficient to redeem the
Warrant called for redemption, such Warrant shall expire and become void and all
rights hereunder and under the Warrant, except the right to receive payment of
the Redemption Price, shall cease.

     (f) If the shares of the Company's Common Stock are subdivided or combined
into a greater or smaller number of shares of Common Stock, the Target Price
shall be proportionally adjusted by the ratio which the total number of shares
of Common Stock outstanding immediately prior to such event bears to the total
number of shares of Common Stock to be outstanding immediately after such event.

     8.  Loss, etc. of Warrant.  Upon receipt of evidence satisfactory to the
         ---------------------
Company of the loss, theft, destruction or mutilation of this Warrant, and of
indemnity reasonably satisfactory to the Company, if lost, stolen or destroyed,
and upon surrender and cancellation of this Warrant, if mutilated, the Company
shall execute and deliver to the Holder a new Warrant of like date, tenor and
denomination.

     9.  Warrant Holder Not Shareholder.  Except as otherwise provided herein,
         ------------------------------
this Warrant does not confer upon the Holder any right to vote or to consent to
or receive notice as a shareholder of the Company, as such, in respect of any
matters whatsoever, or any other rights or liabilities as a shareholder, prior
to the exercise hereof.

     10.  Communication.  No notice or other communication under this Warrant
          -------------
shall be effective unless the same is in writing and is mailed by certified or
registered mail, postage prepaid, addressed to:

          (a) the Company at 3100 World Trade Center, 30 East Seventh Street,
St. Paul, Minnesota 55101, or such other address as the Company has designated
in writing to the Holder, or

                                      -10-
<PAGE>

          (b) the Holder at Two Ingram Boulevard, La Vergne, Tennessee 37809,
Attention: General Counsel, or such other address as the Holder has designated
in writing to the Company.

     11.  Headings.  The headings of this Warrant have been inserted as a matter
          --------
of convenience and shall not affect the construction hereof.

     12.  Applicable Law.  This Warrant shall be governed by and construed in
          --------------
accordance with the internal laws of the State of Delaware, without giving
effect to the principles of conflicts of law thereof.

     13.  Certain Restrictions.  The Company will not, without the consent of
          --------------------
the Holder representing at least a majority of all Warrant Shares issued and
issuable upon the exercise of this Warrant on the date of determination, permit
any amendment to the Company's Certificate of Incorporation or By-laws, if such
amendment would alter the powers, preferences or special rights of the shares of
any class of capital stock of the Company so as to affect the Warrant Shares
adversely in any material respect.

                                      -11-
<PAGE>

     IN WITNESS WHEREOF, VIDEO UPDATE, INC., has caused this Warrant to be
signed by its Chief Executive Officer as of the 11th day of May, 1999.

                                   VIDEO UPDATE, INC.



                                By:/s/ Daniel A. Potter
                                   -----------------------------------------
                                   Daniel A. Potter, Chief Executive Officer

                                      -12-
<PAGE>

                     SCHEDULE I: COMPETITORS OF THE COMPANY
                     --------------------------------------


     The proposed transferee or assignee of Holder must represent and warrant to
both Holder and the Company that he/she/it is not one of the following entities,
a subsidiary or affiliate (as defined in Rule 144 promulgated under the
Securities Act of 1933, as amended) thereof, or a holder of a minimum of 25% of
the outstanding stock thereof, for purposes of Section 5(e) of this Agreement:


     1.   Blockbuster, Inc.
     2.   Viacom, Inc.
     3.   Hollywood Entertainment Corporation
     4.   West Coast Entertainment Corporation
     5.   Video City, Inc.
     6.   Hastings Entertainment, Inc.
     7.   Movie Gallery, Inc.
     8.   Rentrak Corporation

                                      -13-
<PAGE>

                                  SUBSCRIPTION
                                  ------------


     The undersigned, _________________________________________, pursuant to the
provisions of the foregoing Warrant, hereby agrees to subscribe for the purchase
of ____________ shares of the Common Stock of VIDEO UPDATE, INC. covered by said
Warrant, and makes payment therefor in full at the price per share provided by
said Warrant.

Dated:_________________________    Signature

                                   Address



                                 ASSIGNMENT
                                 ----------


     FOR VALUE RECEIVED ______________________________________ hereby sells,
assigns and transfers unto __________________________ the foregoing Warrant and
all rights evidenced thereby, and does irrevocably constitute and appoint
____________________________, attorney, to transfer said Warrant on the books of
VIDEO UPDATE, INC.

Dated:_________________________    Signature

                                   Address



                              PARTIAL ASSIGNMENT
                              ------------------


     FOR VALUE RECEIVED _______________________________________________ hereby
assigns and transfers unto _______________________________________ the right to
purchase __________ shares of the Common Stock of VIDEO UPDATE, INC. by the
foregoing Warrant, and a proportionate part of said Warrant and the rights
evidenced hereby, and does irrevocably constitute and appoint
____________________________________________, attorney, to transfer that part of
said Warrant on the books of VIDEO UPDATE, INC.

Dated:_________________________    Signature

                                   Address

                                      -14-