Corrupted smart group?
I would first check that contacts haven't been manually added to or removed from the smart group. To do this you'll probably need access to the database in order to interrogate the tables. Even though they are smart groups you can still manually add and remove contacts from them and that might be why your seeing unexpected results.

The second test would be to create a new smart group based on the criteria you want and see if you get the result