aptitude может выполнить этот запрос для вас, с ~o («o» для «устаревшего») поиска:
aptitude search ~o
перечисляет пакеты, которые больше не могут быть загружены.
Я не думаю, что есть эквивалент apt-cache search, и я не уверен в синаптике.
Для получения дополнительной информации о поисковых терминах с aptitude, посмотрите раздел на поисковых терминах в справочном руководстве по определению aptitude.