Subscription-licensed copies of Office are associated with the user's Office 365 account. Even if you reinstalled Office, that does not remove the computer from the original users's account. It's Microsoft's servers which are the canonical source of the subscription/activation info.
You need to deactivate the Office instance in the Office 365 Portal. Once that happens, the installed copy of Office will deactivate on the client. In my testing, the client shows a "subscription expired" pop-up the next time Office is opened. However, there might be some lag for the client to detect the deactivation (e.g. If the PC has no Internet connection when it is deactivated).
Once the "subscription expired" message appears, the new user can enter their Office 365 credentials to activate the install in their name.
Office 365 admins can list the activated Office 365 ProPlus installs for a user and deactivate them via the user accounts list in the admin portal. This is a relatively new feature, so you may find a number of outdated blog posts and documentation that says users must deactivate their installs individually.
Regular Office 365 users can self-manage their ProPlus installs by signing into the Office 365 portal (portal.office.com). So they can take care of deactivating old installs on their own without admin intervention.
I must point out that what you are trying to do seems like a pretty pointless exercise, unless the first User has hit their 5 device limit and needs to deactivate an old PC move on to a new one.
One of the major benefits of subscription-licensed Office is you are pretty much always compliant with the licensing, as long as you have Office 365 ProPlus subscriptions for all of your users. In your example above, it does not matter that "UserA" has activated a copy of Office on a PC being used by "UserB". Just make sure you have licenses assigned to all of your users in the Office 365 admin portal.
Also, note that the activation portion of Office 365 ProPlus is independent of the "sign into office" feature (the username in the top right of the Office application). It is perfectly valid for UserB to be signed into Office even though it was activated by UserA.
If UserA leaves your organization, then you just need to unassign their license in the admin portal (which you should be doing anyway as part of your offboarding procedure). That will deactivate UserA's install, requiring UserB to activate.
If the computer is shared by multiple users (a terminal server or a student lab), then you should look into Shared Computer activation. But this is not necessary for regular PC turnover.
In my organization, I haven't bothered with deactivating during normal PC turnover, until a user hits the 5 device limit. Then we login to the portal and clean out old PCs they are no longer using.