The way to remediate unwanted software varies depending on the nature of the unwanted software. Unwanted enterprise software versus PUPs versus malware remediation differs.
From your description, I'm going to assume that the software that you removed was a PUP.
This isn't software that's explicitly malicious, it's just "unwanted". Typically, running the uninstaller is enough to remove the active components in the software.
The best way to remove the software entirely, including old registry entries, folders, environmental variables, and so on, is to obtain a list of all system changes that the PUP makes on installation. Search the name of the software and locate a removal list. Often, you can find a list of all changes that a program makes when it is installed. (FN 1) Then, you can undo them manually.
The alternative is to run software designed to remove unwanted software. Many anti-malware vendors offer a product for free. If you search for "pup removal tool" you should get multiple options. Naturally, you want to examine the vendor offering the software to make sure it is legitimate offering, and not more adware masquerading as anti-malware. Typically these tools can remove PUPs and avoid the need to reformat your machine.
Other, more extreme measures are always an option - as others have said, you can rollback restore points, or reformat the entire operating system. Typically this isn't necessary with PUPs.
- If you cannot find a remediation list, you will need to forensically generate one, manually. Fist you will need to generate a clean state system, install the unwanted software, then compare the current system state with the pre-installation state. There are many tools to help you do this, most of which are a part of a good malware forensics suite. (PUP's aren't necessarily malware, but malware forensics uses the same tools and skills as non-malware program forensics.) This is a long and arduous process, and is outside the scope of this question to cover in depth. See additional reading for resources on learning this process.
Practical Malware Analysis: The Hands-On Guide to Dissecting Malicious Software by Michael Sikorski and Andrew Honig
Flare VM - an example of a malware analysis tool suite.