Design keys which satisfy two conditions. You will be selling these keys with your software. In the software test for only one condition. Users will anyway reverse-engineer your code and generate fake keys for your software, but these keys will satisfy only one condition that you checked for.
In your web application test for the second condition too. This way you can find illegitimate keys and block illegal copies of your software from auto-updating. You can also try to disable those copies.
You will have to blacklist even original keys which are being used by many users at a time (this happens when someone shares/publishes his key).
wont it be difficult to do it with the load of user privacy policy we have to follow? Think that makes people get away easy.
I don’t know of any privacy policy norms that this technology violates. Can you point out some?