I don't think I have a solid solution, but I am curious to know why ("from time to time") you erase and re-install Leopard? To update an OS from scratch means updating a myriad of native apps as well, not to mention 3rd parties. Your OS must be time-warping..
My next move would be to Target with another Mac and hopefully find and correct a fixable hard drive problem.
Good luck, I hope you mend your ailment.