Eu experimentei algo semelhante e descobri que a instalação do pacote funcionaria muito bem, mesmo que apt-cache policy package dissesse que não estava disponível e exibiu a mensagem de erro que você está relatando, mas com N: em vez de E: . (No entanto, apt-cache search package retorna a saída vazia para mim, em vez da mensagem de erro.)
A execução de strace em apt-cache revela que ele abre apenas um subconjunto dos arquivos em /var/lib/apt/lists - especificamente, parece ignorar meu repositório particular, talvez porque tenha um nome de arquivo um pouco engraçado ( myserver.internal_%7etripleee_repo_Packages ).