Remove package's dependencies (does not remove package):
brew deps [FORMULA] | xargs brew remove --ignore-dependencies
Remove package:
brew remove [FORMULA]
Reinstall missing libraries:
brew missing | cut -d: -f2 | sort | uniq | xargs brew install
This problem is more robustly solved by something like
brew rmtree