Don't replace the hard drive unless you can afford to pay for a hard drive that you probably don't need.
When the system starts, does chkdsk start automatically?
How long have you left the system on step 5 (sometimes it takes a long, long time to finish - I'd suggest letting it run overnight)?
What do you do to bypass it?
Is there any mention of a "dirty bit" or a "flag" being set?
Try this free diagnostic memory test: Memory Diagnostics
(read the details at the link)
Then run CHKDSK without any parameters - this will tell you if there's any problems (but won't try to correct them). Then check the log file and post it's results here for us to have a look at:
Go to Start and type in "eventvwr.msc" (without the quotes) and press Enter
Expand the Windows logs heading, then select the Application log file entry.
Double click on the Source column header.
Scroll down the list until you find the Chkdsk entry (wininit for Win7) (winlogon for XP).
Copy/paste the results into your next post.