If you were running Lion 10.7.2 or 10.7.3 and have a complete Time Machine backup on a locally-connected external drive, then you might be able to boot into Lion Recovery directly from the Time Machine backup. This is a new feature.
This support article:
About the OS X Lion v10.7.2 Update
The OS X Lion v10.7.2 Update includes Safari 5.1.1 as well as fixes that:
Enable booting into Lion Recovery from a locally connected Time Machine backup drive.
I don't know further details.
Wow! I had no idea my time Machine backup might contain the recovery software to format and load Lion. I will give that a try before using the thumb drive option. I just hope the new, unformatted drive that is installed will not interfere with any boot sequence that will prevent my external drive from doing the work. My external drive has the GUID partition scheme but has three separate partions for Time Machine, HFS +, and NTFS. It has worked well for the past couple of years.
The OP has a 2008 MBP, which is not new enough for this.
Lion Internet recovery in the absence of a recovery partition on disk has to be done via the Mac's firmware. All new Macs have this capability, and there are EFI firmware updates available for a number 2010 and 2011 Macs, but there is no such EFI firmware update available for a 2008 MBP.
MacBook Pro (13-inch, Early 2011)
MacBook Pro (15-inch, Early 2011)
MacBook Pro (17-inch, Early 2011)
iMac (21.5-inch, Mid 2011)
iMac (27-inch, Mid 2011)
MacBook (13-inch, Mid 2010)
MacBook Pro (13-inch, Mid 2010)
Mac mini (Mid 2010)
MacBook Pro (15-inch and 17-inch, Mid 2010)
iMac (21.5-inch and 27-inch, Mid 2010)
MacBook Air (11-inch and 13-inch, Late 2010)
I believe the Time Machine method will work fine. I started by holding the option key and choosing the Time Machine Partition choice. Clicking on Time Machin offered me the option to install Lion. I assume it will do so with an unformatted intenal drive. I will see what happens in a couple of weeks and reply here. Oops, I think I gave credit to myself rather than jsd2 for helping me out.