Denied access to contact after editing contact

Users with access limited to edit individuals in specific smart groups get the following error when editing contacts: "Your Individual contact record has been saved. You do not have the necessary permission to view this contact."

Upon checking the individual contacts that were edited I noticed they weren't listed as being a part of any group. I believe there is some strangeness with the way smart groups work that users don't always have full permission to access contacts in those groups because the contacts don't always appear to be in those groups.

The user has access when viewing the contact when all contacts from the smart group are returned, but somehow after editing the user is denied access to that contact - until you view the members of the smart group again and that contact shows up again.