MS has mostly moved away from product keys in their software. I'm not sure the entire ins and outs of your situation but in general software is now tied to the MS account of the user. For example, if you buy a license for Windows 10 and install it then it'll ask for a product key. You enter the product key to confirm the edition you have. At that point the product is tied to your MS account, not the product key. The next time you install Windows you could enter a product key but there is no reason to. Instead you just skip that process and when you connect your MS account it figures out that you have a license for Windows and it is now licensed.
So, if I understand what they told you correctly, you don't need product keys. At most they need the product key when they first install the software unless you already associated it with their account. After that they just log in and it knows about the license because it is associated with the account. AFAIK you don't need to do anything special in an RD situation as each user logs into the system and then tries to use Office their account is validated to ensure they have an associated license.
But this is all just my understanding based upon my own experience. I've not had to do anything with RD and multiple users though.