Ah, so I see that anything associated to the scope is reavaluated whenever anything else in the scope changes. Here's a further modification based on yours that keeps the criteria on the controller.
[1] http://plnkr.co/edit/JYyUvyh30e5L9KwVjDW2?p=preview
[2] http://plnkr.co/edit/ffYb14JjgSip5BTITILS?p=preview
edit: much happier with this version than the one I started with, thanks
edit: added example [2] which doesn't require a watch but still uses the service to do the filtering (because in my app it's actually an ajax call)