No lo has eliminado todo, por eso no te deja instalarlo de nuevo. Cuando se instala una extension en joomla 2.5, hay una tabla llamada _extensions, tu prefijo + _extensions, por ejemplo dxzsf_extensions, donde se crean los datos de cada extension instalada. Edita la tabla desde phpmyadmin y busca plugins, modulos y el componente, relacionado con virtuemart y elimina esos datos de esa tabla.
Gestor de contenidos Joomla para crear tu web
