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.