Excluding in search doesn't work
You should use the custom search "Include / Exclude Search" that does exactly what you want

civicrm/contact/search/custom?csid=4&amp;reset=1 on my install, likely the same custom search id on your install