I am having the same problem. I have one customer with this issue. Here is what I have identified so far.
Her credit card expired in April, her subscription processed and her payment was declined, it was also declined on two subsequent 12hr retries. Here is the error reject from those three rejections.
Braintree (Credit Card) Payment Failed (Status code 2046: Declined (51 : DECLINED) Transaction ID XXXXXXXX) Order status changed from Pending payment to Failed.
Then she updated her credit card and this is the new rejection which happened 3 times on 12hr retries:
Braintree (Credit Card) Payment Failed (Subscription Renewal: payment token is missing/invalid.) Order status changed from Pending payment to Failed.
So after these three additional tries, the order ended up in the failed status after this and her subscription was automatically put on hold. I didn’t notice this, and it remained on hold until she contacted yesterday wondering where her subscription was. I couldn’t figure out what happened, so I had her remove her original credit card and add a new one. I am still getting the same token missing/invalid response when I process a renewal under the new card.
The token in Woo matched the Braintree token before I had her change the card. It also matches after the new card, but it is a different token. I can see on Braintree the first three rejections on 4/23 and 4/24, but I do not see the token missing/invalid rejections on Braintree. So Woo must be stopping the transaction before it is even sent to the processor.
The original transactions were April 23-25th, and the new transactions were today.
I found this link which describes the same issue happening with the square plugin. That developer stated it was fixed, perhaps you can get some additional information from him. https://www.ads-software.com/support/topic/missing-payment-token/