Gmail – How to filter the unread Gmail messages that aren’t labeled X or Y

First part: yes you can start from the search box and then when you see the results use More/Create Filter.

Second Part: The problem is that that if you include the phrase "label" in the search string and try to make the filer you will get the forllowing warning.

Filter searches containing "label:", "in:", "is:", or stars criteria (i.e. "has:yellow-star") are not recommended as they will never match incoming mail.

Do you still wish to continue to the next step?**

I have seen nothing that allows you to order the filters, or tell it to stop processing other filters if this one is applied. These types of rules/actions are typically seen in other email systems. Remember the strength of the labels is the ability to file a conversation under multiple labels, so telling it to ignore other rules isn't an action that is needed very often.

The two filter method will work, If it comes from address 1 give it one label. If it comes from the second address then give it label 2. You can even use the not to make sure that only those from address 1 go to label 1.

This answer assumes that all of the automated emails are sent from the same address.

I'm not sure how you've created your filter, but try filtering by the from: field only. If the automated sender's address is always something like no-reply@domain.com then set up your filter to filter on:

from: no-reply@domain.com

This will make sure all automated email will hit the filter. Then, when someone else replies to that address, the new sender's email will be different from the one listed in the filter, and allow it to hit the inbox as normal.