Smart Group criteria disappearing or changing
There was a set of nasty bugs that fit the description of what you're talking about throughout 2015:

https://issues.civicrm.org/jira/browse/CRM-18155

https://issues.civicrm.org/jira/browse/CRM-18435

CRM-18435 in particular is getting a fix in the August 3rd release of CiviCRM.  You can patch it now if you know how (patch is linked from the ticket above) but otherwise upgrade next week.

To give a big-picture overview - smart groups rely on the underlying form (in this case, Search Builder) not changing.  For a while, there wasn't really awareness that changing the form would break smart groups.  In fact, I have a patch that hasn't yet made it into CiviCRM here because someone pointed out that a benign-seeming change could break a smart group.

Now that there's awareness (and automated tests!) around that, those issues are going away.