An off the top of my head suggestion:
as the boot menu, setting it up per normal for booting into XP/Vista.
For the recovery part, first create partition images using Partition Saving
Create two Partition Saving boot floppies, one has an autoexec.bat that will restore the XP partition, the other to restore the Vista partition (Partition Saving has rather extensive options, the archive has a description and examples on how to create an options file).
So the autoexec.bat on one floppy might have 'savepart -r -f XP.cfg', to restore XP. On the other floppy it might have 'savepart -r -f Vista.cfg' to restore the Vista partition.
Then turn the two floppies into images using WinImage
(30 day trial), (eg. RestoreXP.img and RestVsta.img), and use GRUB4DOS to boot them from it's menu.
This should give you a boot menu with your four choices and costs nothing except a little reading and preparation.