I don't disagree with your assertion about the state of Homebrew, but I wanted to point out the `leaves` subcommand.
brew leaves:
Show installed formulae that are not dependencies of another installed formula.
I'm not sure if it persists this state or simply calculates it on-the-fly by enumerating your installed formulae. But it does seem like the same data or functionality could be used to prevent your uninstalled-deps scenario.
Hmm... Interesting. I don't think that "brew leaves" truly solves the problem, though, since the list it generates will include explicitly-installed leaves in addition to no-longer-needed dependencies. It can help narrow the list of potential candidates for removal, though, which is nice.
