The chkdsk that runs because of a perceived problem...at boot...does not perform a complete check.
My analogy would be that it attempts to address the wound...by putting a bandage on it.
Chkdsk is activated because there is either a perceived problem with the file system (NTFS) or the hard drive. The 3-stage chkdsk that runs can overcome some of these situations, but not all.
When this chkdsk at boot occurs on my systems, I interpret that as a message that I need to run the chkdsk /r command, which is a 5-stage process and includes efforts to recover data from bad sectors on the hard drive (which is not done when the automatic 3-stage chkdsk runs).
If that doesn't solve the problem, then I do a diagnostic (long/extended test) on the hard drive, using the hard drive manufacturer's tool for doing such.
If you have a Microsoft XP CD, then you can run chkdsk /r on a system that won't boot...from the Recovery Console of the XP CD.
How to use CHKDSK in the XP Recovery Console - http://pirules3.14.googlepages.com/recovery_console_chkdsk
If you don't have a MS XP CD, then you can download the Recovery Console and run the chkdsk /r command from there.
Download Recovery Console, Bootable ISO - http://www.webtree.ca/windowsxp/repair_xp.htm
. Note that this is an .iso file and must be burned to CD in order to be useable on a typical system.
How to successfully burn or write an ISO-image to cd or dvd - http://iso.snoekonline.com/iso.htm
In the event that the chkdsk /r command is unable to resolve whatever is wrong, I suggest the respective hard drive diagnostic.
I would also suggest that you move any data (not program) files which you value...from the hard drive with problems...before attempting any thing.