It sounds to me like it's time to get a new vendor to work with.
I know that may not be feasible, but I think you have some legitimate points with their software not being an easy thing to update or remove.
I don't think there is an 'easy' way out of this. You have the right information on how to go about removing software configurations, however, from your description, it appears your vendor has done some sloppy work.
I do not know how many users are affected by this, but it appears you'll need to have your users manually remove the software from their devices and try a new software configuration to get the new version to their device. Sorry, I wish there was another way, but I don't think there is.