Você removeu (removeu) apenas o pacote base do php5. Php binary vem com php5-cli, então você provavelmente não removeu outros pacotes php. Você pode verificar isso executando:
# dpkg -S 'which php5'
php5-cli: /usr/bin/php5
Se você não obtiver o nome do pacote, é possível que o php5 esteja instalado a partir do código-fonte.
Outra opção é que, quando você executa o 'apt-get purge php *' - existem alguns arquivos php * em seu diretório de trabalho atual que resultariam em expansão do shell e não executariam o comando que você espera executar. Por exemplo, se você tivesse arquivos php-foo, php-bar no seu CWD no momento da execução do apt-get purge php *, isso teria se expandido para:
apt-get purge php-foo php-bar
Também é aconselhável listar todos os pacotes do php para verificar o que você está realmente instalando no seu sistema:
# dpkg -l | grep php | sort