As a Linux desktop user for the last 4 years, I can attest to never having to reformat. I installed Debian about 1.5 years ago (last time I formatted my Linux OS HD) and didn't even have to reformat to upgrade the distribution to a new version (yay for apt-get). My file server/firewall/internet gateway runs Linux as well, and has an uptime of some 120 days. In my experience, these installations have never becomes slower or cruftier or displaying weird errors... it does seem to be unique to Windows.
redarrow: Maybe you should get a friend who's got his RH/WinXP installation to work to help you out. I'm guessing that its resizing your Windows XP partition thats screwing things up. This is indeed a part which can go wrong... Maybe you should get a cheap second hand HD with about 10GB to install RH Linux on... that way you won't have to touch your Windows XP partition. Or try out the
Knoppix LiveCD... to see if Linux is worth it for you.