It sounds like you were using version 4.0.1 or earlier than that. There were some known bugs in the uninstall process of very early versions like that.
Note that if you are still seeing the above error, then you have not finished all the uninstall steps either. You still must remove all of the VaultWiki files from your system or attackers might be able to exploit vulnerabilities even though it is not installed in the Add-On Manager. Looking at XenForo's code, it will not attempt to run any admin-search handler that does not exist on the file system.