You are totally right. Search module needs the Feeds & Notifications module to be active. You are also correct that there is no warning about this. We wanted to implement some warning dialogs when a module is deactivated, but there are more urgent features. Seeing that there are users that experience this problem, we will add additional text as you suggested in the module description for the next internal build.
I hope this will prevent such problem in the future.
Do you want to have your say in the Sitefinity development roadmap? Do you want to know when a feature you requested is added or when a bug fixed? Explore the Telerik Sitefinity CMS Ideas&Feedback Portal
and vote to affect the priority of the items