As promised, Apple has begun selling Mac OS X Lion on flash USB sticks in its retail stores. The US$69 drives (seventy dollars?!) contain a full install of the operating system and look much like the recovery drives that ship with MacBook Airs.
You can use the little doohickey to install Lion (or reinstall it), attempt a repair with Disk Utility or run Time Machine. They're not yet available online, so stop by your local Apple Store to buy one. Happy recovery!