You could even graft it down onto FAT32 from NTFS. It will start in partial safe-mode and start reinstalling low-level devices, and could at some point ask for the CD. So just make an image and come up with a way to unpack the image onto hda1 from Linux.

I'll bet it's easier with XP, because the boot process is saner and you can boot from the CD and do a repair. Just make the ERD that XP needs. That'll restore Windows booting, then you start Linux from a bootdisk and re-establish Linux booting with Windows as a secondary boot option.

Both my laptops work this way.