Но, по всей видимости, где-то эти пакеты у Вас apt-ах есть.
Для проверки:
> apt-cache show bacula7-client

apt ищет во всех своих sources + в установленных пакетах.
Это поведение, боюсь, исправить будет нереально.

(Ответ для ildar на комментарий #1)
> Но, по всей видимости, где-то эти пакеты у Вас apt-ах есть.

В Conflicts у bacula11-*

ооо! это меняет дело!
хмм, Антон, есть идеи, как это поправить?

(In reply to ildar from comment #3)
> ооо! это меняет дело!
> хмм, Антон, есть идеи, как это поправить?

Добавить --no-all-versions в /usr/share/bash-completion/completions/apt-cache в _apt_cache_packages в `apt-cache --no-generate pkgnames`

(Ответ для ildar на комментарий #3)
> ооо! это меняет дело!
> хмм, Антон, есть идеи, как это поправить?

Виталий предложил исправление:

(Ответ для Vitaly Chikunov на комментарий #4)
> (In reply to ildar from comment #3)
> > ооо! это меняет дело!
> > хмм, Антон, есть идеи, как это поправить?
> 
> Добавить --no-all-versions в
> /usr/share/bash-completion/completions/apt-cache в _apt_cache_packages в
> `apt-cache --no-generate pkgnames`

ildar, будете исправлять?

боюсь, сейчас сделать и протестировать — никак, аврал. Недели через две.

$ apt-cache --no-generate --no-all-versions pkgnames|grep php8.0
i586-php8.0-xhprof
php8.0-pdo-devel
i586-apache2-mod_php8.0
php8.0-xhprof
apache2-mod_php8.0

но эти пакеты уже давно удалены из репозитория. Оно похоже конфликты находит. Тут только apt чинить.

(In reply to Anton Farygin from comment #7)
> $ apt-cache --no-generate --no-all-versions pkgnames|grep php8.0
> i586-php8.0-xhprof
> php8.0-pdo-devel
> i586-apache2-mod_php8.0
> php8.0-xhprof
> apache2-mod_php8.0
> 
> но эти пакеты уже давно удалены из репозитория. Оно похоже конфликты
> находит. Тут только apt чинить.

 $ apt-cache pkgnames --no-all-names | grep php8.0 | wc -l
 0

Но тогда не будет работать поиск по виртуальным пакетам - Provides.

Думаю что текущее поведение с учётом возможностей apt - оптимально.
Конечно, надо исправить, но всё-таки исправлять надо в apt, добавив в него нужный инструмент для получения списка Provides в пакетах.