I only started on this quest when I had problems burning a boot DVD of InstallESD. I figured the file was corrupt.
Method 1: Use a Mac with app store that has not downloaded Lion. Using the App Store account that originally purchased Lion, start your download. Apple allows the use of Lion on all your Mac for $30.
Method 2: Move Install Mac OS X Lion.app that you've perviously downloaded to the trash. The system will ask for the admin password. Now simply launch App Store and go to Purchases. Note the change from Installed to Install.
[crarko adds: Not a lot of new ground covered here, but there were a few submissions of variation of this hint so I took the most complete of the lot. What worked for me was to make sure I had a backup copy of the downloaded Lion installer on another drive. Then when the installer self-destructs you can simply put another copy from the backup on the next machine, rather than downloading again.]

