We just had a comments model (in mongoose) that had an array of subcomments (MongoDB arrays are awesome). Therefore the "trees" (not really trees as we implemented it) could only have one level of indentation ... but that's all we wanted anyways.
Can't you do it every time someone votes? The scores aren't dependent on any other items other than their own votes, so each time it gets a new vote, you rescore it and it will drop or go up on the front page accordingly.
Sure, but with a system that is active (like HN), there would be enough votes coming in frequently enough to handle the ranking updates and account for time increases without needing to hit the system every 5 minutes.