Subscription to User-saved searches Required functionality:


User can filter nodes based on certain relevant custom fields. 
User can save filter criteria as a named set. 
User can view and edit these sets of filter criteria. 
User can "subscribe" to changes based on his saved sets of filter criteria and get email notifications containing links to only the newly matching nodes.


Can I build such subscriptions with mostly out-of-the-box functionality of Rules and related modules?

Subscriptions depending addressfield field is a related question, but the poor lad did not get an answer.
Conceptually the business logic you want to complete is possible using Drupal. Finding a way to make this scale to a very large website -- I leave as a project for you.

Start by looking at Saved Searches and Views Saved Search or Views Save. These modules let you save a search with a simple name for later re-use. Some of these modules allow per-user saved searches.

You could then create a Queue using the Queue API in Drupal to periodically process the resultsets of these searches. Or even use the Relation module to store heuristics on these resultsets.

Create a cron task using hook_cron or Rules Scheduler to periodically process the resultsets and have Rules to send off emails about new changes in the saved searches. Functions like views_get_results (if you use views_saved_searches) can help you to get these results.

So in general yes it's possible with Drupal -- scaling all this to a very large amount of  users is either an infrastructure problem or something (i think) "Drupal" shouldn't do in the long run ...