The only time when the
memberOf overlay will be activated is if you modify a member in a group. So, the only way to "trick" it into updating the
memberOf attributes would indeed be to remove all users from their groups and re-add them, as you suggested.
An alternative would be to use an external tool to synchronize groups and their members's entries.
You could write your own script for this - something along the lines of "for each group, read the members, for each member, run a LDAP "modify" operation to "add" a value to the memberOf attribute of that member's entry.
Or, probably more reliable, you could use a tool like LSC (LDAP Synchronization Connector) which has pretty much everything already done: you just need to configure the mapping you want. The trick with LSC is to use the same LDAP server as both source and destination, and running through all users to make sure that the memberOf attribute contains the list of groups that results from searching all groups for member=. The LSC website has a tutorial to do this, sort of, but it's a bit outdated.