O argumento para o comando de manipulação de pacotes é uma expressão regular, não um padrão curinga de shell. Portanto, emacs23* significa qualquer pacote que contenha emacs2 como substring (já que 3* corresponde à string vazia).
apt-get remove '^emacs23'