O mysql-server do mysql-server é um meta-pacote que se vincula a pacotes como o mysql-server-5.5 mysql-client-5.5. Se você desinstalou os pacotes meta, e não os pacotes específicos da versão, o mysql ainda está instalado.
Eu tinha o servidor mysql em execução. Eu parei e removi (apt-get remove o mysql-server mysql-client)
Eu então removi manualmente os diretórios:
/var/lib/mysql
/var/run/mysqld
Eu reiniciei. Mas quando eu digito mysql, recebo a seguinte mensagem:
ERROR 2002 (HY000): Can't connect to local MySQL server through socket '/var/run/mysqld/mysqld.sock' (2)
Eu recebo a mesma mensagem de erro quando digito service mysql stop
Isso significa que o servidor mysql ainda está em execução. Como eu me livre disso completamente e paro o processo. Meu sistema operacional é o servidor Ubuntu 12.04.
Você deve verificar com dpkg -l que você não tem nenhum pacote mysql instalado no servidor. Parece haver algum utilitário MySQL que tenta se conectar ao seu servidor. Remova todos os pacotes mysql com apt-get e você poderá inicializar de maneira limpa.