I haven't dealt that much with XP, and this sounds like a joke for me (I mean, it's not funny you have to go through this type of thing, but it sounds just so dump that windows-linux dual boot installation can be this difficult many times...I had problems too when I started my very first linux back in the days)
Where did you choose to install your boot loader, by the way? In MBR, or in some partition? I'm not sure if this has anything to do with these, but..one never knows. At least in older Windows versions, installing windows often destroyed linux's bootloader, and because Windows's own bootloader didn't boot linux, I had to do some tricks (that was win98 then) to get over this problem, especialy if I had to reinstall windows (which wasn't that rare thing)
Did you let Mandrake do all the configuration "automatically" or something, or did you do them "by hand"?