What you'll want to delete are keys located in HLKM\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall that have 'PHP' in the DisplayName string. Just navigate to that Uninstall key, do a Find for 'PHP', and delete any key that corresponds to a PHP installation (the 'key' is the part on the left that contains the GUID for the installation... {05BB2EC5-68Ef-...} etc.)
After that, it might be easier for you to a) install PHP using the .zip package (as Weedpacket described), since I personally think is much cleaner, gives you more control over the install process, allows you to configure extensions and configurations exactly the way you want, etc., or b) install an all-in-one package such as WAMP. Personal suggestion being option a, of course.
