If your existing members are getting a new recurring contribution you could potentially check for a new recurring contribution instead of a new membership? I think that would solve the issue.
If you try and it does not you might try something like:
a first rule to check for relevant new memberships and add them to a group
a second rule that adds them to a ...