quando você fez apt-get remove php5
acabou de remover o meta-pacote.
Para listar todos os pacotes php5 que você instalou você precisa fazer: dpkg -l '*php5*'
e depois remover todos os instalados, ou apenas apt-get remove php5-common
, que removerá o pacote "base" que é a dependência de todos os outros pacotes php5 no cadeia de dependências e, assim, remover todos os pacotes php5 instalados.
Felicidades, Ondrej