Starting with Coveo for Sitecore 4.0, some event handlers were added to specifically handle this use case.
Coveo.SearchProvider.config file, the
EntityEventHandler class is hooked on many Sitecore events.
user:deleted should all trigger a security cache update for this specific user, which means its roles should be expanded and new security applied.
In the October 2016 release (4.0.450, later hotfixed to 4.0.704), some events were added to handle the roles which fix your problem:
role:rolesRemoved should trigger a security cache update when a specific role changes.
So the solution would be to upgrade or code your own handler on this event to refresh the cache.
As for your comment:
... it seems that security changes aren't necessarily immediately pushed up, unless the item in question is published.
The update of the document forces an expansion of the users from that document, which picks up the new changes.
After the October release, a bug was found in which the
role:usersAdded were not properly updating the security cache. So the user was still pushed with its updated roles but was not refreshed until the next security cache update.
This bug was fixed in the January 2017 release (4.0.895), tagged with the issue number SC-1480.