Desculpe responder minha própria pergunta, mas acho que descobri ...
A eliminação falhou porque o mysqld ainda estava em execução (e escutando na porta 3306).
# lsof -i TCP:3306
COMMAND PID USER FD TYPE DEVICE SIZE/OFF NODE NAME
mysqld 12629 mysql 17u IPv4 78816 0t0 TCP localhost:mysql (LISTEN)
Eu deveria ter matado o processo antes de desinstalar. Depois de matar o processo, eu poderia reinstalar o MySQL / MariaDB:
# kill -9 12629
# apt-get install mariadb-server mariadb-client
# systemctl restart mysql
# systemctl restart apache
Espero que ajude alguém ...