The problem is this: I have a 320gb HDD splitted in 4 partitions. When I first installed Windows XP I formatted the HDD in 3 (Windows system partition, Media partition and another one I left for Linux). However Linux requires another partition for swap. Everything was just fine. One day Windows stopped working and I tried re-installing it. After the system was ready to start, Windows failed to boot with "NTLDR is missing" message. I tried to recover the Master boot record, even replaced NTLDR manually - nothing worked. I read that in order a HDD to be partitioned in more than 3 parts the so called "extended" partitions must be created. I think this may cause the problem but I don't want to wipe out everything (I have more than 100 GB of books most of which are not available anymore in the same locations I have downloaded them)
I'm pretty sure you're okay with 4 partitions. That you need to use an extended partition with logical partitions within it, to go over 4.
I'd try Super Grub Disk to get your Windows system booted.
If, by chance, you're actually running Windows Vista or 7, you could use the awesome tool EasyBCD to set up a great boot menu.
However, since you're dealing with XP, once you've confirmed that you can get Windows booting again, I'd just in to Linux and work on getting windows booting working with grub again. I believe the command "update-grub" will regenerate the grub menu on Ubuntu systems. I suggest you explore that a bit.
In terms of Swap in Linux, you can function without any swap. Granted, it's generally worth having some swap space available. You can generate a swap file, rather than partition if you want. I suspect the partition is more efficient in terms of speed. If you want instructions on how to generate a swap file in Linux, let me know.