Some vpn clients do not cleanly uninstall. This is particularly true of so called "free" vpn that load ads and other crap.
You can check the forums for the particular vpn you are using and see if people have similar problem solutions.
I always load vpn on my router lately after having similar issues just updating a vpn client.