"There must be a easy solution to this. Like in ms when it runs a scandisk and repairs errors on reboot."
The equivalent Linux program is fsck. See:
"Should I boot from the cd and try to repair the installation ?"
Yes. Instead of:
fsck.reiserfs rebuild tree
try the following command (assuming that your reiserfs partition is /dev/hda3):
Be prepared. Create a LifeBoat CD.