Here's how I did it for each and every skin:
1. Uninstall poker client
2. Delete poker client directory -- install program won't do this
3. Delete any shortcuts/folders on the desktop and/or on the Start menu
4. click on Start > Run and type regedit
5. Do a search (CTRL-F, I think) for
<ul type="square">[*] party (for Party Poker) [*] empire (for Empire Poker)[*] multipoker (for Multipoker)[*] eurobet (for Eurobet)[*] cepoker (for Eurobet)[*] intertops (for Intertops Poker)[/list]6. Delete anything that comes up for those search terms. It's best to delete the whole node (i.e. folder).
NOTE: You will get other hits for 'party'. Only delete those folders/keys that are obviously for Party Poker. You will also get some hits as a result of Pokertracker, you can safely ignore those (as long as it's part of a Pokertracker folder/key).
7. Go into C:\WINDOWS\Prefetch and delete any files that appear to have been created as a result of poker client software. Most will be obvious. Might have to delete some generic ones as well (i.e. install.exe is part of the name).
That should do it. Works for me everytime. This is on XP by the way.