This is what scares me about Apple's move away from having DVD instal disks (and DVD drives for that matter!!!)... So, I have a time machine back-up, but its not bootable, my internal drive dies, I replace the drive, now what?
You restart holding command R, and get an Internet recovery option, no restore partition is needed.
That works only if your machine is new enough to support Internet Recovery. And a machine that new should hot experience a total hard drive failure in the first place. If it did it might well still be under warrantee, in which case you would be better advised to return the computer to Apple and have them replace the drive and the system. If you have an older machine without recourse to Internet Recovery, a total drive failure would necessitate reinstalling Snow Leopard from an install DVD, updating to OS X 10.6.8 and then, with the Apple ID you used to buy Lion, re-download and install Lion again. This would insure that you get a Recovery HD partition on the new drive. Then you might be able to restore your system to it's pre-crash state from a Time Machine backup. Note I say "might"; Time Machine can be fickle about recognizing a system as the one it was built from.
A better solution altogether is to keep an updated clone of your system. Not only would this be bootable in the meantime, while you are waiting for a new hard drive to be delivered, but you could be certain of restoring the system to the new drive - once you've installed Lion to get the Recovery HD partition back. This whole rigamarole is more complex than the previous method of installing from optical media. It has no doubt reduced the cost to Apple of providing system upgrades, assuming the bandwidth involved actually costs less than providing installation DVDs. And they have passed this savings on to users, drastically reducing the cost of OS upgrades. But I'm not sure the cost savings justifies the additional complexity. This may be fun and games to power users, but I doubt the "average" user feels so sanguine about it. In fact, I doubt the average user would even be aware of all of this until a problem arises and they have to consult their local Mac guru for a solution.
Of course the Internet download paradigm works well with Apple's new optical drive free MacBook Air and Pro RD models. With them its all of a piece. For users of other Mac models, which still have an optical drive, the system is far less holistic. The problem is that Apple adopted the new process in one fell swoop, with not viable transition options. That's why I made a point early on of following the tutorials to create a Lion install disk on both a DVD and a thumb drive. There is now an excellent piece of donation-ware, Lion DiskMaker, that makes the process relatively easy and painless. I recommend it to anyone who has any concerns about reinstalling Lion/Mountain Lion in the future.