I am going to throw out a few possibles for you to mix-n-match and choose from.
1.) My suspicions were wrong. The disk is probably just fine. Which would indicate some undefined file system corruption.
2.) When was the last time you did a really thorough anti-virus scan of all files? Once-upon-a-time there was a cute little virus that planted itself in the file system. The way it did this was change the length of a sector from 512 to some other value. I forget now what length but it is unimportant at this point. This left another sector too short. chkdsk would fix this by marking the two non-standard sectors as defective, however when you reboot, a stub that is placed in the 1st sector, (boot sector), triggers the virus to re-plant itself and the process begins anew. A good way to get an indication of this virus is to run chkdsk and reboot twice and check the storage available. Run chkdsk again and do the same thing. If you have this or some variation of this virus you will never get it to stay fixed and the storage space will just continue to be reduced each time. This is a very hard virus to get rid of once you are infected. It is hard to find and hard to fix without using mass destruction techniques.
3.) It could be just some common file system corruption, which ntfs is prone to do, for no obvious reason, from time to time. It is just a coincidence that it doesn't seem to affect the operation of the system, at least not at this point in time.
1.) Stay with Windows on this drive and do nothing. System is working... at least for now.
2.) Off-load your operating system and data as is, re-constitute a fresh ntfs file system, and put everything back on the drive. At the same time you can allow space for the Linux install. If it is a virus problem you will still have it however.
3.) Backup your data, (only data, no executables or system files, and then only after they have been scanned), dd the entire drive and start over with a fresh set of partitions and new XP install. This is the drastic fix but the only one that is a 99.9% sure thing.