You may have uninstalled wine, but you left all the configuration files behind, including the wine registry, so reinstalling just brought you back to where you started.
Try running regedit, do a search for the program name (and whatever other keywords you may think of relating to the program, such as the maker), and remove any entries that you find. Also, go into the location where you installed it and delete any files and folders that may have been left behind. Sometimes windows uninstallers leave lots of stuff behind, so you have to clean things up manually.
Basically, you just do the same things you would do on windows.