After IsGenuineEx() returns TA_FAIL, are you then checking IsActivated() to see if the customer is activated (but failed to connected to the servers to reverify their license)?
If not, do that. A customer cannot use another key to activate when they already have a different key activated. My guess is that this is what's happening.
Only after doing that, then check if the customer is copying & pasting the key correctly. That they have the right key and that they're putting it in the right place. Do a remote login with the customer to determine that