O erro não significa que você ainda tem o servidor MYSQL em execução. Na verdade, se o cliente não puder se conectar a ele, provavelmente você não o executará.
Você ainda tem o cliente disponível para execução: mysql
Você pode descobrir o pacote onde o mysql está, com:
dpkg -S 'which mysql'
Em seguida, remova-o, se você realmente quiser fazer isso.