If you want to replace your HD and absolutely need the recovery partition, why not
- do a clean install, which will create the recovery partition;
- transfer your clone back to the new Lion installation
Presto, you're back in business, complete with a recovery partition.