Você não pode remover o OpenJDK 7 porque não está instalado . Se você estiver tentando remover o OpenJDK 6, tente sudo apt-get remove openjdk-6-jdk
ou sudo apt-get remove default-jdk
.
apt-cache search
mostra apenas os pacotes disponíveis, não os pacotes que você instalou. Para isso, tente sudo dpkg --list
; sudo dpkg --list | grep -i jdk
mostrará todos os pacotes relacionados ao JDK instalados em seu sistema.