Я не совсем уверен, что вы понимаете, «некоторые части Java остаются в моей системе», но запуск этих двух команд подскажет вам, что установлено относительно java и VM openjdk.
dpkg --get-selections | grep java
dpkg --get-selections | grep jdk
Множество пакетов «java» - это, фактически, библиотеки и привязки, вам, вероятно, не все равно. Ядро java находится в commons, я думаю.
Кроме того, возможно, ваша проблема возникает из оставшихся конфигурационных файлов ... не забывайте apt-get purge ваши пакеты!