I describe this problem as "broken as designed". The problem is that the AND condition of your search applies to the same person but not to the same fact for the same person. So if one fact for one person satisfies one part of the AND and a different fact for the same person satisfies the other part of the AND, then your search gets a match because both conditions are applied to the same person. Most typically, that is not the desired behavior. You really want both of your search conditions to be applied to the same fact for the same person, not just for the same person.
The search where I used to run into this problem on a regular basis was even simpler than yours. I would search for something like "census date equals 1850" AND "census place contains texas". I would get a match if for a person whose actual data was that their 1850 census was in Tennessee and their 1860 census was in Texas. This would give the same kind of false match as you got with your search.
I solved my problem by switching over from RM's built-in census fact to using census facts of my own design which are specific to census year - one fact type for the 1850 census, a different fact type for the 1860 census, etc. It's not the solution I would have preferred, but it does work quite well. The only possible problem I have with it is that I could still have a search problem if an individual was actually enumerated twice in the same census year. It's rare, but it does happen.
I really can't think of a good solution for your problem. There is a longstanding wish list item requesting that RM provide a way to for multiple search conditions to be applied to the same fact, and there is no way to know when or even if this wish will be fulfilled.
Jerry
