In the process of ditching Vista, I reformatted the drive back to the factory default. As I rebuild the system, I tested the recovery partition to ensure that it was still working. It seems the secret is to keep the recovery partition as the last partition on the drive, but it must be a primary partition.
This means the disk is arrange similar to the following:
1 Primary Windows XP-M
2 Primary Linux /boot
4 Extended
5 Logical FAT-32 (data)
6 Logical NTFS (Win Apps)
7 Logical Linux LVM (F7)
3 Primary Recovery
The big trick is going to come when I try to re-install Vista as Logical partition number 8. Oooo... Won't that be interesting.