Well we do a few things. We have our registry key which as you said can be deleted. But we also store info in one of our tables, again the field we store info in is encrypted, so if they uninstall and reinstall then restore their data, the program will find out they did this. Futhermore, we drop a small file with additional information into their windows directory. This file is not deleted by our uninstaller.

Hope this helps, no program is 100% full proof. Really the best you can do is be creative with ways to stop users from cheating you. If you use enough methods then eventually you'll stop the casual (and perhaps intermediate) cracker.

Good luck,
Bryan