Bearshare is, AFAIK, a legitimate (in the broadest sense of the term) p2p file sharing application.
Unless the source of the installer file was “dodgy”, that is, corrupted, not from the home page, it should not be infected.
In other words, using “add/remove programs” to uninstall it, and then rebooting, should have removed it.