Why can't you just disable vbSEO, why are you trying to uninstall it? You may be causing yourself a headache for no reason. There is only two things I can see as a potential problem if it doesn't alter default key tables in vbulletin. The .htaccess files as @ShawneyJ suggested and maybe a bitfield.xml file if they have altered the default bit-fields in a weird way.
Remember: I do not run vBSEO so the wisdom you are receiving, is equivalent to how much you are paying for it.