Você pode procurar por pacotes obsoletos instalados, instalados localmente ou com o repositório de origem desabilitado)
aptitude search '?narrow(?installed, ~o)'
Além disso, se você quiser os dois + ppa obsoletos:
aptitude search '?narrow(?installed, ~Oppa | ~o)'
Referência: aptitude - Referência do termo de pesquisa