How can I create or recreate a Lion recovery partition?
First, open a Terminal.

Status before:

$ diskutil list
/dev/disk0
  #:                       TYPE NAME                    SIZE       IDENTIFIER
  0:      GUID_partition_scheme                        *128.0 GB   disk0
  1:                        EFI                         209.7 MB   disk0s1
  2:                  Apple_HFS Macintosh HD            127.8 GB   disk0s2


Get Lion Recovery Update v1.0 (431.91 MB)

Mount RecoveryHDUpdate.dmg

$ hdiutil attach ~/Downloads/RecoveryHDUpdate.dmg


Extract data from RecoveryHDUpdate.pkg

$ pkgutil --expand /Volumes/Mac\ OS\ X\ Lion\ Recovery\ HD\ Update/RecoveryHDUpdate.pkg ~/Desktop/RHD


Mount RecoveryHDMeta.dmg (in the RecoveryHDUpdate.pkg package)

$ hdiutil attach ~/Desktop/RHD/RecoveryHDUpdate.pkg/RecoveryHDMeta.dmg


Run tool that will finally resize current partition and create recovery

$ ~/Desktop/RHD/RecoveryHDUpdate.pkg/Scripts/Tools/dmtest ensureRecoveryPartition / /Volumes/Recovery\ HD\ Update/BaseSystem.dmg 0 0 /Volumes/Recovery\ HD\ Update/BaseSystem.chunklist
Creating recovery partition: finished


Status after:

$ diskutil list
/dev/disk0
  #:                       TYPE NAME                    SIZE       IDENTIFIER
  0:      GUID_partition_scheme                        *128.0 GB   disk0
  1:                        EFI                         209.7 MB   disk0s1
  2:                  Apple_HFS Macintosh HD            127.2 GB   disk0s2
  3:                 Apple_Boot Recovery HD             650.0 MB   disk0s3