Por que você tem tanta certeza de que não precisa disso? Talvez outros pacotes dependam disso, ele não é usado exclusivamente para configurar um servidor mysql, alguns programas gerenciam seus bancos de dados internos usando-o por exemplo.
Agora, para responder à sua pergunta, o primeiro passo é descobrir qual pacote instalou esses arquivos:
$ dpkg -S /usr/bin/mysql
mysql-client-core-5.5: /usr/bin/mysql
Essa é a saída de uma máquina virtual Ubuntu 14.04, a sua provavelmente será uma versão diferente, mas o mesmo princípio se aplica. Agora você sabe o nome do pacote e pode removê-lo manualmente.
Basicamente, os dois pacotes que você removeu são ambos meta pacotes que apontam para outros pacotes. Então, quando você os removeu, você removeu apenas o pacote fictício e não tudo que estava instalado com eles. Para remover tudo relacionado ao mysql, execute isto:
sudo apt-get remove --purge mysql-*