EXHIBIT 10.1 Execution Copy COMMON UNIT REDEMPTION AGREEMENT This COMMON UNIT REDEMPTION AGREEMENT (this "Agreement"), dated as of March 12, 2003, among VALERO L.P., a Delaware limited partnership (the "Partnership"), and UDS LOGISTICS, LLC, a Delaware limited liability company (the "Holder"). WHEREAS, the Holder now holds 4,424,322 common units representing limited partnership interests in the Partnership (the "Common Units"); WHEREAS, the Partnership desires to increase the public float of the Common Units; WHEREAS, the Partnership has entered into an underwriting agreement of even date herewith (the "Equity Underwriting Agreement") with Lehman Brothers Inc., Goldman, Sachs & Co., Morgan Stanley Incorporated, Salomon Smith Barney Inc., UBS Warburg LLC, Credit Suisse First Boston LLC, RBC Dain Rauscher Inc., and Sanders Morris Harris, Inc. (collectively, the "Underwriters") pursuant to which the Partnership is publicly offering (the "Public Offering") for cash (i) 5,750,000 Common Units and (ii) in the event the Underwriters exercise their over-allotment option pursuant to the Underwriting Agreement, up to an additional 862,500 Common Units, in each case pursuant to the Partnership's registration statement on Form S-3 (No. 333-89978) (as amended to the date hereof, the "Registration Statement") and a prospectus supplement (together with the prospectus included in the Registration Statement, the "Prospectus") filed under Rule 424 under the Securities Act (as defined herein); WHEREAS, Valero Logistics Operations, L.P., a 100%-owned subsidiary of the Partnership, has entered into a purchase agreement of even date herewith (the "Purchase Agreement"), with J.P. Morgan Securities Inc., Barclays Capital Inc., Mizuho International plc, RBC Dominion Securities Corporation, Scotia Capital (USA) Inc., Sun Trust Capital Markets and Tokyo-Mitsubishi International plc (collectively, the "Initial Purchasers") pursuant to which the OLP is offering for cash $250 million aggregate principal amount of its 6.05% senior notes in a private placement (the "Private Placement") in accordance with Rule 144A under the Securities Act pursuant to a private placement memorandum; WHEREAS, the Partnership intends to cause the OLP to borrow approximately $34 million under its amended revolving credit facility (the "Credit Facility"); WHEREAS, the Holder desires to transfer to the Partnership, and the Partnership desires to redeem from the Holder, 3,809,750 of the Common Units held by the Holder (the "Units") upon the terms and conditions hereinafter set forth (the "Redemption"); and WHEREAS, the Partnership and the Holder desire to make certain representations, warranties and agreements in connection with the Redemption; NOW THEREFORE, in consideration of the mutual covenants, conditions and agreements set forth herein, and for good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties hereto agree as follows: 1. Redemption of Units. Subject to the terms and conditions and in reliance upon the representations and warranties herein set forth, the Holder agrees to transfer to the Partnership, and the Partnership agrees to redeem from the Holder, at a price per unit of $35.19 (the "Redemption Price"), which is equal to the net proceeds per unit received by the Partnership in the Public Offering, after underwriting discounts and commissions, but before expenses, the Units on the Closing Date (as defined below), provided that only the proceeds from the Private Placement and/or the borrowing under the Credit Facility but not the proceeds from the Public Offering shall be used for the cash amount payable to the Holder as the Redemption Price. 1.1 The closing ("Closing") of the redemption of the Units shall take place at the offices of Andrews & Kurth L.L.P., at 10:00 a.m., local time, or as soon as practicable thereafter, on March 18, 2003 (the "Closing Date"). 1.2 At the Closing, the Holder shall assign and transfer to the Partnership all its right, title and interest in and to the Units free and clear of all liens or other limitations or restrictions and deliver to the Partnership the certificate or certificates representing the Units, duly endorsed in blank or accompanied by separate stock powers so endorsed. 1.3 The Partnership shall pay the aggregate Redemption Price on the Closing Date, without deduction, by wire transfer of immediately available funds from the account into which the proceeds of the Private Placement and/or the borrowings under the Credit Facility, but not the proceeds from the Public Offering, have been deposited, to an account of the Holder (the number for which account shall have been furnished to the Partnership at least one business day prior to the Closing Date). 1.4. Simultaneously with the Redemption, the Partnership will pay the amount of $2,857,312.50 to Riverwalk Logistics, L.P. (the "General Partner") in redemption of the corresponding portion of its general partner interest in order to maintain the General Partner's general partner interest in the Partnership at 2% giving effect to the Redemption. 2. Representations and Warranties of Holders. The Holder hereby represents and warrants to, and agrees with the Partnership, as applicable, that: 2.1 Existence and Power. The Holder is a limited liability company duly formed, validly existing and in good standing under the laws of the State of Delaware and has all requisite corporate power and authority to execute and deliver this Agreement and consummate the transactions and perform each of its obligations contemplated hereby. 2.2 Authority; Approvals. (a) The execution and delivery of this Agreement by the Holder, the consummation by the Holder of each of the transactions and the performance by the Holder of each of its obligations contemplated hereby have been duly and properly authorized by all necessary corporate action on the part of the Holder. This Agreement has been duly executed and delivered by the Holder, and, assuming the accuracy of the representations and warranties of the Partnership in Section 3 hereof, constitutes the valid and legally binding obligation of the Holder, enforceable against it in accordance with its terms, subject, as to enforceability, to bankruptcy, insolvency, reorganization, moratorium and other similar laws of general Page 2 applicability relating to or affecting creditors' rights and to general principles of equity (regardless of whether such enforceability is considered in a proceeding in equity or at law. (b) The execution and delivery of this Agreement by the Holder and the consummation of each of the transactions and the performance of each of the obligations contemplated hereby (i) do not conflict with or violate (whether with or without notice or a lapse of time or both), require the consent of any Person to or otherwise result in a material detriment to the Holder under its organizational documents or any agreement to which it is a party or any law or order applicable to it, in each case in a manner that could reasonably be expected to materially hinder or impair the completion of any of the transactions contemplated hereby or have a material adverse effect on the business, properties, condition (financial or otherwise), liabilities or prospects of the Holder; and (ii) do not impose any penalty or other onerous condition on the Holder that could reasonably be expected to materially hinder or impact the completion of any of the transactions contemplated hereby. As used herein, the term "Person" means a natural person, corporation, limited liability company, venture, partnership, trust, unincorporated organization, association or other entity. (c) No approval from any Governmental Entity is required by or with respect to the Holder in connection with the execution and delivery by the Holder of this Agreement, the performance by the Holder of its obligations hereunder or the consummation by the Holder of the transactions contemplated hereby, except for any such approval the failure of which to be made or obtained (i) has not impaired and could not reasonably be expected to impair the ability of the Holder to perform its obligations under this Agreement in any material respect and (ii) could not reasonably be expected to delay in any material respect or prevent the consummation of any of the transactions contemplated by this Agreement. As used herein, the term "Governmental Entity" means any agency, bureau, commission, authority, department, official, political subdivision, tribunal or other instrumentality of any government, whether (i) regulatory, administrative or otherwise; (ii) federal, state or local or (iii) domestic or foreign. 2.3 Ownership of Units. The Holder is the record and beneficial owner of the Units, free and clear of any lien and any other limitation or restriction with full right and authority to deliver the same hereunder, and will transfer and deliver to the Partnership on the Closing Date valid title to the Units, free and clear of any lien and any such other limitation or restriction (except as the nonassessability of the Units may be affected by matters described in the Partnership's registration statement on Form S-1 (No. 333-43668) under the caption "The Partnership Agreement--Limited Liability," which is incorporated by reference into the Partnership's registration statement on Form 8-A (File No. 1-16417) (the "Form 8-A")). 2.4 Independent Investigation. The Holder (a) has the requisite knowledge, sophistication and experience in order to fairly evaluate a disposition of the Units, including the risks associated therewith, and (b) has adequate information and has made its own independent investigation and evaluation to the extent it deems necessary or appropriate concerning the properties, business and financial condition of the Partnership to make an informed decision regarding the transfer of the Units pursuant to this Agreement. 3. Representations and Warranties of the Partnership. The Partnership hereby represents and warrants to, and agrees with the Holder, that: Page 3 3.1 Existence and Power. The Partnership is a limited partnership duly organized, validly existing and in good standing under the laws of the State of Delaware and has all requisite entity power and authority to execute and deliver this Agreement and consummate the transactions and perform each of its obligations contemplated hereby. 3.2 Authority; Approvals. (a) The execution and delivery of this Agreement by the Partnership, the consummation by the Partnership of each of the transactions and the performance by the Partnership of each of its obligations contemplated hereby have been duly and properly authorized by all necessary partnership action on the part of the Partnership. This Agreement has been duly executed and delivered by it and, assuming the accuracy of the representations and warranties of the Holder in Section 2 hereof, constitutes the valid and legally binding obligation of the Partnership, enforceable against it in accordance with its terms, subject, (i) as to enforceability, to bankruptcy, insolvency, reorganization, moratorium and other similar laws of general applicability relating to or affecting creditors' rights and to general principles of equity (regardless of whether such enforceability is considered in a proceeding in equity or at law) and (ii) to equitable principles of general applicability relating to the availability of specific performance, injunctive relief, or other equitable remedies. (b) The execution and delivery of this Agreement by the Partnership and the consummation of each of the transactions and the performance of each of the obligations contemplated hereby (i) do not conflict with or violate (whether with or without notice or a lapse of time or both), require the consent of any Person to or otherwise result in a material detriment to the Partnership under its organizational documents or any agreement to which it is a party or any law or order applicable to it, in each case in a manner that could reasonably be expected to materially hinder or impair the completion of any of the transactions contemplated hereby or have a material adverse effect on the business, properties, condition (financial or otherwise), liabilities or prospects of the Partnership; and (ii) do not impose any penalty or other onerous condition on the Partnership that could reasonably be expected to materially hinder or impact the completion of any of the transactions contemplated hereby. (c) No approval from any Governmental Entity is required by or with respect to the Partnership in connection with the execution and delivery by the Partnership of this Agreement, the performance by the Partnership of its obligations hereunder or the consummation by the Partnership of the transactions contemplated hereby, except (i) as have been obtained under the Securities Act of 1933, as amended, and the rules and regulations of the Securities and Exchange Commission (the "Commission") thereunder (collectively, the "Securities Act"), and as may be required under state securities or blue sky laws in connection with the Public Offering and (ii) for any such approval the failure of which to be made or obtained (x) has not impaired and could not reasonably be expected to impair the ability of the Partnership to perform its obligations under this Agreement in any material respect and (y) could not reasonably be expected to delay in any material respect or prevent the consummation of any of the transactions contemplated by this Agreement. Page 4 4. Conditions to Closing. 4.1 Conditions to Obligations of the Partnership. The obligation of the Partnership to redeem the Units hereunder is subject to the satisfaction of the following conditions: (a) The closings contemplated in (i) Section 4 of the Equity Underwriting Agreement and (ii) Section 3 of the Purchase Agreement shall have been consummated; (b) The Holder shall have performed in all material respects all of its obligations hereunder required to be performed by it on or prior to the Closing Date; (c) No action, claim, suit, hearing, complaint, demand, injunction, litigation, judgment, arbitration, order, decree, ruling or governmental investigation or proceeding shall be pending or threatened by any court or governmental or regulatory agency or body, and no such court or governmental or regulatory agency or body shall have issued any injunction, judgment or order, which shall remain in effect, that would prevent consummation of the Redemption; provided, however, that the parties hereto shall use their reasonable best efforts to have any such injunction, judgment or order vacated or reversed; (d) The representations and warranties of the Holder contained in this Agreement and in any certificate or other writing delivered by the Holder pursuant hereto shall be true in all material respects at and as of the Closing Date, as if made at and as of such date; and (e) The Partnership shall have received a certificate signed by a duly authorized officer of the Holder to the effects set forth in clauses (b) and (d) above. 4.2 Conditions of Obligations of the Holder. The obligation of the Holder to consummate the transactions contemplated hereby is subject to the satisfaction of the following conditions: (a) The closings contemplated in (i) Section 4 of the Equity Underwriting Agreement and (ii) Section 3 of the Purchase Agreement shall have been consummated; (b) The Partnership shall have performed in all material respects all of its obligations under this Agreement required to be performed by it on or prior to the Closing Date; (c) No action, claim, suit, hearing, complaint, demand, injunction, litigation, judgment, arbitration, order, decree, ruling or governmental investigation or proceeding shall be pending or threatened by any court or governmental or regulatory agency or body, and no such court or governmental or regulatory agency or body shall have issued any injunction, judgment or order, which shall remain in effect, that would prevent consummation of the Redemption; provided, however, that the parties hereto shall use their reasonable best efforts to have any such injunction, judgment or order vacated or reversed; (d) The representations and warranties of the Partnership contained in this Agreement and in any certificate or other writing delivered by the Partnership pursuant hereto Page 5 shall be true in all material respects at and as of the Closing Date, as if made at and as of such date; and (e) The Holder shall have received a certificate signed by a duly authorized officer of Valero GP, LLC on behalf of the Partnership to the effects set forth in clauses (b) and (d) above. 5. Governmental Filings. The Holder shall, or cause its affiliates, as applicable, to make all filings with any Governmental Entity required by the Holder in connection with the execution and delivery by the Holder of this Agreement or the consummation by the Holder of the transactions contemplated hereby, including without limitation, all filings with the Commission required pursuant to the Exchange Act (as defined herein). 6. Indemnification. 6.1 Indemnification by the Partnership. The Partnership will indemnify and hold harmless the Holder, its respective officers, directors and each person who controls the Holder within the meaning of Section 15 of the Securities Act and Section 20 of the Securities Exchange Act of 1934, as amended, and the rules and regulations of the Commission thereunder (collectively, the "Exchange Act") against all losses, claims, damages and liabilities (including, without limitation, the legal fees and other expenses incurred in connection with any suit, action, proceeding or any claim asserted) arising out of or based on: (a) any inaccuracy or breach as of the date of this Agreement or as of the Closing Date of any representation or warranty made by the Partnership in Section 3 of this Agreement or in any certificate delivered by the Partnership pursuant to this Agreement; and (b) the breach or default in the performance by the Partnership of any covenant, agreement or obligation to be performed by the Partnership pursuant to this Agreement. 6.2 Indemnification by the Holder. The Holder will indemnify the Partnership, its officers, directors and each person who controls the Partnership within the meaning of Section 15 of the Securities Act and Section 20 of the Exchange Act, against all losses, claims, damages and liabilities (including, without limitation, the legal fees and expenses incurred in connection with any suit, action, proceeding or any claim asserted) arising out of or based on: (a) any inaccuracy or breach as of the date of this Agreement or as of the Closing Date of any representation or warranty made by the Holder in Section 2 of this Agreement or in any certificate delivered by the Holder pursuant to this Agreement; and (b) the breach or default in the performance by the Holder of any covenant, agreement or obligation to be performed by the Holder pursuant to this Agreement. The liability of the Holder pursuant to this Section 6.2 shall be limited to the aggregate Redemption Price. Page 6 6.3 Indemnification Procedures. If any suit, action, proceeding (including any governmental or regulatory investigation), claim or demand shall be brought or asserted against any person in respect of which indemnity may be sought pursuant to the preceding paragraphs of this Section 6, such person (the "Indemnified Person") shall promptly notify the person or persons against whom such indemnity may be sought (each an "Indemnifying Person") in writing, and such Indemnifying Persons, upon request of the Indemnified Person, shall retain counsel reasonably satisfactory to the Indemnified Person to represent the Indemnified Person and any others the Indemnifying Persons may designate in such proceeding and shall pay the reasonable fees and expenses of such counsel related to such proceeding. In any such proceeding, any Indemnified Person shall have the right to retain its own counsel, but the fees and expenses of such counsel shall be at the expense of such Indemnified Person and not the Indemnifying Persons unless (i) the Indemnifying Persons and the Indemnified Person shall have mutually agreed to the contrary, (ii) the Indemnifying Person has failed within a reasonable time to retain counsel reasonably satisfactory to the Indemnified Person or (iii) the named parties in any such proceeding (including any impleaded parties) include both an Indemnifying Person and the Indemnified Person and representation of both parties by the same counsel would be inappropriate due to actual or potential differing interests between them. It is understood that no Indemnifying Person shall, in connection with any proceeding or related proceeding in the same jurisdiction, be liable for the reasonable fees and expenses of more than one separate firm (in addition to any local counsel) for all Indemnified Persons, and that all such fees and expenses shall be reimbursed as they are incurred. No Indemnifying Person shall be liable for any settlement of any proceeding effected without its written consent, but if settled with such consent or if there be a final judgment for the plaintiff, each Indemnifying Person agrees to indemnify any Indemnified Person from and against any loss or liability by reason of such settlement or judgment. Notwithstanding the foregoing sentence, if at any time an Indemnified Person shall have requested an Indemnifying Person to reimburse the Indemnified Person for fees and expenses of counsel as contemplated by the second and third sentences of this paragraph, such Indemnifying Person agrees that it shall be liable for any settlement of any proceeding effected without its written consent if (i) such settlement is entered into more than 90 days after receipt by such Indemnifying Person of the aforesaid request and (ii) such Indemnifying Person shall not have reimbursed the Indemnified Person in accordance with such request prior to the date of such settlement. No Indemnifying Person shall, without the prior written consent of the Indemnified Person, effect any settlement of any pending or threatened proceeding in respect of which any Indemnified Person is or could have been a party and indemnity could have been sought hereunder by such Indemnified Person, unless such settlement includes an unconditional release of such Indemnified Person from all liability on claims that are the subject matter of such proceeding. 6.4 Contribution. The Partnership and the Holder agree that it would not be just and equitable if contribution pursuant to this Section 6 were determined by pro rata allocation. The amount paid or payable by an Indemnified Person as a result of the losses, claims, damages and liabilities referred to in this Section 6 shall be deemed to include any legal or other expenses incurred by such Indemnified Person in connection with investigating or defending any such action or claim. Notwithstanding the provisions of this Section 6, in no event shall the Holder be required to contribute any amount in excess of the amount of the aggregate Redemption Price received by it. No person guilty of fraudulent misrepresentation Page 7 (within the meaning of Section 11(f) of the Securities Act) shall be entitled to contribution from any person who was not guilty of such fraudulent misrepresentation. 6.5 Full Force and Effect. The remedies provided for in this Section 6 are not exclusive and shall not limit any rights or remedies which may otherwise be available to any indemnified party at law or in equity. The indemnity and contribution agreements contained in this Section 6 and the representations and warranties of the Partnership and the Holder set forth in this Agreement shall remain operative and in full force and effect regardless of (i) any termination of this Agreement, (ii) any investigation made by or on behalf of any party hereto, its respective officers or directors or any person controlling such party and (iii) consummation of the Redemption. 7. Expenses. Whether or not the transactions contemplated by this Agreement are consummated, each of the Partnership and the Holder shall pay its own expenses incurred in connection with the negotiation and preparation of this Agreement and the consummation of the transactions contemplated hereby. 8. Miscellaneous. 8.1 Notices. All notices, requests and other communications to any party hereunder shall be in writing (including facsimile transmission) and shall be given, If to the Holder, to: UDS Logistics, LLC c/o Valero Energy Corporation One Valero Place San Antonio, Texas 78212 Attention: Vice President--Legal Services Fax: (210) 370-5889 If to the Partnership, to: Valero L.P. One Valero Place San Antonio, Texas 78212 Attention: Corporate Secretary Fax: (210) 370-2409 All such notices, requests and other communications shall be deemed received on the date of receipt by the recipient thereof if received prior to 5:00 p.m. in the place of receipt and such day is a business day in the place of receipt. Otherwise, any such notice, request or communication shall be deemed not to have been received until the next succeeding business day in the place of receipt. By notice given in accordance with this Section 8.1 to the other party, any party may change its address for the receipt of notices under this Agreement. Page 8 8.2 Amendments and Waivers. Any provision of this Agreement may be amended or waived if, but only if, such amendment or waiver is in writing and is signed, in the case of an amendment, by each party to this Agreement, or in the case of a waiver, by the party against whom the waiver is to be effective. Waiver of any term or condition of this Agreement by a party shall not be construed as a waiver of any subsequent breach or waiver of the same term or condition by such party, or a waiver of any other term or condition of this Agreement by such party. No failure or delay by any party in exercising any right, power or privilege hereunder shall operate as a waiver thereof nor shall any single or partial exercise thereof preclude any other or further exercise thereof or the exercise of any other right, power or privilege. 8.3 Assignment. Neither this Agreement nor any of the rights, interests or obligations under this Agreement shall be assigned or delegated, in whole or in part, by operation of law or otherwise by any of the parties without the prior written consent of the other parties. 8.4 Successors and Assigns. The provisions of this Agreement shall be binding upon and inure to the benefit of the parties hereto and their respective successors and permitted assigns. 8.5 Entire Agreement; No Third-Party Beneficiaries. This Agreement constitutes the entire agreement and supersedes all prior agreements and understandings, both written and oral between the parties with respect to the subject matter of this Agreement. Except as specifically set forth or referred to herein, nothing herein expressed or implied is intended or shall be construed to confer upon or give to any Person, the parties hereto, and their permitted successors or assigns, any rights or remedies under or by reason of this Agreement. No third party is entitled to rely on any of the representations, warranties and agreements contained in this Agreement, and the Partnership and the Holder assume no liability to any third party because of any reliance on the representations, warranties and agreements of the Partnership and the Holder contained in this Agreement. 8.6 Governing Law. This Agreement shall be governed by and construed in accordance with the law of the State of Texas, without reference to its conflict of laws principles. 8.7 Severability. Any term or provision of this Agreement which is invalid or unenforceable in any jurisdiction shall, as to that jurisdiction, be ineffective to the extent of such invalidity or unenforceability without rendering invalid or unenforceable the remaining terms and provisions of this Agreement or affecting the validity or enforceability of any of the terms or provisions of this Agreement in any other jurisdiction. If any provision of this Agreement is so broad as to be unenforceable, the provision shall be interpreted to be only so broad as is enforceable. 8.8 Termination. Notwithstanding any provision in this Agreement to the contrary, this Agreement shall terminate in the event the Equity Underwriting Agreement or the Purchase Agreement is terminated in accordance with the terms contained therein. 8.9 Public Announcements. Each party agrees that, except as may be required by applicable law or any listing agreement with any national securities exchange, such party will Page 9 not issue any press release or make any public statement with respect to this Agreement or the transactions contemplated hereby without obtaining the prior written consent of the other party. 8.10 Interpretation. When a reference is made in this Agreement to a Section, such reference shall be to a Section of this Agreement unless otherwise indicated. The captions and headings appearing at the beginning of the various sections of this Agreement are for convenience of reference only and shall not be given any effect whatsoever in the construction or interpretation of this Agreement. Whenever the words "include", "includes" or "including" are used in this Agreement, they shall be deemed to be followed by the words "without limitation." 8.11 Counterparts. This Agreement may be executed in one or more counterparts, each of which shall be deemed an original, but all of which together shall constitute one and the same instrument. Any party may execute this Agreement by the delivery of a facsimile signature, which signature shall have the same force and effect as an original signature. Any party that delivers a facsimile signature shall promptly thereafter deliver an originally executed signature to the other party; provided, however, that the failure to deliver an original signature page shall not affect the validity of any signature delivered by facsimile. Page 10 IN WITNESS WHEREOF, each of the parties hereto has caused this Agreement to be executed by its duly authorized officer as of the date first written above. VALERO L.P. By: Riverwalk Logistics, L.P. its General Partner By: Valero GP, LLC its General Partner By: /s/ CURTIS V. ANASTASIO -------------------------------- Curtis V. Anastasio President UDS LOGISTICS, LLC By: /s/ RAYMOND GADDY -------------------------------- Raymond Gaddy President Page 11