I would prefer the latter way. I often have posts that are relevant when published but not very useful some time later. I could add a hidden category to which I add those posts when they cease to be relevant and exclude that category from related posts. Those articles would not show up in related posts and there would be more visibility for more useful articles.
If I needed to exclude related posts from appearing in posts of some category I could use WordPress conditional tags to do that (I am inserting the code manually).