Vous avez raison: «Je crains qu’il ne vienne» et «Il y a longtemps que je ne l’ai vu» sont effectivement des situations différentes.
Pour «Je crains qu’il ne vienne», on a:
Je crains qu’il ne vienne (c’est-à-dire, je crains sa présence): la subordonnée a un sens positif, et le ne est dès lors clairement explétif, donc inutile du point de vue logique;
Je crains qu’il ne vienne pas (c’est-à-dire, je crains son absence): la subordonnée a un sens négatif, et la négation ne … pas est évidemment justifiée.
Pour «Il y a longtemps que je ne l’ai vu», les possibilités sont:
Il y a longtemps que je l’ai vu
Il y a longtemps que je ne l’ai vu
Il y a longtemps que je ne l’ai pas vu
Il y a longtemps que je ne l’ai plus vu
Ici, à la différence de «Je crains qu’il ne vienne», le sens reste le même pour les quatre possibilités, qu’il y ait une négation ou non! La subordonnée est toujours positive (je l’ai vu, mais il y a longtemps), et on pourrait donc être tenté d’affirmer que non seulement le ne, mais aussi le ne…pas et le ne…plus sont explétifs, car en contradiction avec le caractère positif que la subordonnée garde dans les quatre cas. D’où sans doute la recommandation dans le manuel de Papy.
Mais il me vient un doute. La subordonnée est-elle réellement positive? Si on considère p.ex. la phrase: Il y a longtemps que j’attends, et qu’on la met en regard de Il y a longtemps que je l’ai vu, la subordonnée de la deuxième phrase nous apparaît alors négative. En effet:
Il y a longtemps que j’attends = j’ai attendu pendant une longue durée
Il y a longtemps que je l’ai vu = je ne l’ai pas vu pendant une longue durée.
Autrement dit, la négation — il y a longtemps que je ne l’ai (pas, plus) vu — se justifie en logique, autant que la phrase sans négation. Ce qui voudrait dire également que l’expression il y a longtemps que peut s’entendre de deux manières différentes: soit on se réfère à un certain point dans le temps où un fait positif (je l’ai vu) a eu lieu, soit on envisage plutôt la durée qui s’est écoulée depuis et où le fait positif n’a plus eu lieu (sens négatif de la subordonnée).
Au demeurant, des phrases du type «il y a longtemps que je n’ai plus fait telle chose» sont très courantes, et je n’ai jamais entendu affirmer qu’elles étaient incorrectes.
Ai-je été suffisamment embrouillé?