J'ai donc modifié le source à partir de l'idée de Galain qui m'a d'ailleurs envoyé un programme corrigé, ce dont je le remercie.
Si j'ai le temps je reprendrai l'algo de MichelPiesyk en l'adaptant aux listes (plus besoin de tableau) et en m'affranchissant du principe alphabétique, ce qui pourrait donner :
- dès qu'une liste atteint 32000 éléments, on la divise en deux listes en transférant la moitié des éléments dans la seconde (le point faible de l'algo !) ;
- on met à jour une table de hachage qui contient les premier et dernier élément de chaque liste ;
- lors d'un ajout, on cherche dans la table de hachage dans quelle liste doit aller le nouvel élément ;
- on vérifie qu'il n'y est pas déjà (sinon, doublon), puis on l'ajoute (en réalité, l'insère puisque la liste est automatiquement triée par sorted=true) ;
- etc.
Je pense néanmoins que le dernier algo qui est dans le source peut difficilement être dépassé (50000 éléments en 4 secondes) et je remercie tous les participants pour leurs idées.

@Billotmi
J'ai donc ajouté l'algo qui utilise une chaîne de caractères pour rechercher les doublons puis je la transforme en tableau que je trie par le QuickSort. Les performances restent cependant inférieures à l'algorithme d'origine. A la fin, la transformation en tableau par split() puis le Quicksort n'ont qu'un effet minime sur la performance(j'ai fait un essai en les supprimant, pour ne garder que la recherche des doublons) : visiblement, c'est la constitution de la chaîne puis la recherche par instr() qui prennent du temps.

@Billotmi
j'avais pensé au tableau fixe avec une variable correspondant au nombre d'éléments réels, variable incrémentée à chaque ajout. Or j'ai constaté que le Redim Preserve est vraiment peu gourmand en ressources car les différences de traitement sont négligeables de l'ordre de quelques secondes) :
- pour 10000 chaînes -> 5 sec au lieu de 6
- pour 30000 chaînes -> 41 sec au lieu de 42
- pour 50000 chaînes -> 94 sec au lieu de 96
comme on perd la souplesse du tableau dynamique, j'ai donc préféré conserver le redim preserve.
------
La méthode avec QuickSort est ici tout à fait anecdotique et c'était pour répondre @Galain car je ne l'ai ajoutée après coup (l'intérêt du tri par insertion est justement de se passer... d'un tri).
A vrai dire, le tri ici n'est utile que pour pouvoir effectuer une recherche dichotomique d'un éventuel doublon qui n'est possible... que lorsque le tableau est trié.
L'intérêt de l'algorithme que j'ai déposé ici vient du fait qu'il permet de connaître en une seule opération s'il s'agit d'un doublon (et dans ce cas de le traiter à part) ou sinon de récupérer l'indice d'insertion de l'enregistrement dans le tableau.
Le problème de la lenteur vient du "comment décaler un tableau vers le haut" rapidement. VB sait le bien le faire en quelques secondes quand on remplit une liste ou une combo triée jusqu'à 32000 éléments.
Maintenant, il n'y a peut-être pas d'autre solution que de patienter.
----------
L'utilisation de instr sur une chaîne de caractères semble prometteuse. J'ai fait simplement un essai avec :
a$ = String(40000, "12345") + "67890" + String$(10000, "12345")
MsgBox Str$(InStr(a$, "67890"))
et la recherche est pratiquement instantané. En générant une chaîne de 500 millions de caractères cela prend quelques secondes, l'élément à chercher se trouvant aux 9/10 de la chaîne ; au delà j'ai un message d'erreur pour mémoire insuffisante.
Si j'ai le temps, j'essaierai d'ajouter cet algo au programme (mais dans ce cas, il ne s'agira plus d'un tri - simplement une recherche des doublons, ce qui correspond d'ailleurs à mon problème initial).

J'ai mis le source modifié en ligne.
Je dois respecter une contrainte qui est que les doubles doivent être refusés d'entrée dans la liste (et non pas enlevés après le tri par une recherche des doubles). J'ai donc testé le QuickSort après chaque ajout d'enregistrement mais les performances sont nettement dégradées par rapport à l'idée d'origine car un QuickSort, tout récursif qu'il soit, reste nettement plus lent qu'un décalage séquentiel d'enregistrements vers le haut. J'ai consulté l'article de Wikipedia sur l'Introsort, mais ce n'est qu'une amélioration du Quicksort qui ne changerait rien au problème. Lequel reste posé - si quelqu'un a une idée.
A vrai dire j'ai réalisé ce petit programme pour un module de suppression des fichiers doublons sur un disque dur d'archives (même nom, date et taille parmi plusieurs centaines de milliers de fichiers - eh oui ! les archives s'accumulent au fil du temps et on duplique souvent des dossiers entiers alors qu'il n'y a qu'un fichier modifié dedans) : or il faut que le premier fichier trouvé soit considéré comme "le bon" et les autres comme des doublons à supprimer. Je peux mettre le programme en ligne si ça intéresse quelqu'un (mais je crois qu'on en trouve déjà sur Code Source).

Effectivement, un Quicksort est capable de trier 50000 éléments en moins de 2 sec, mais ce qui m'intéresse c'est de pouvoir stocker les doublons à part et j'ai du mal à gérer cela dans la recursivité du Quicksort. Je ne connais pas l'introsort et je vais faire quelques recherches car c'est peut-être la solution à mon problème (tester par dichotomie si l'élément est présent avant de lancer le tri récursif). Si j'ai le temps, je mettrai en ligne le source modifié. Merci donc à Galain et TarodMaster.

Bonne source qui me sera utile. Très claire, bien commentée et facilement réutilisable. Merci.

Je me demandais aussi à quoi correspondait cette liste des code de pages (la variable de type Long laissait entendre qu'il y en avait plusieurs milliers).
Pour le savoir, j'ai donc placé le code ci-dessus dans un module et le code ci-dessous dans une feuille sur laquelle se trouve un bouton Command1 et une liste Liste1 :

Private Sub Command1_Click()
Dim i As Long
Call f_CodePage_Init
For i = 0 To g_CodePageNbr - 1
    Liste1.AddItem Str$(g_CodePageLst(i).Id) + " " + g_CodePageLst(i).Name
Next i
End Sub

S'affiche ainsi la liste des codes supportés (55 sur ma machine). Ce qui se présente comme ceci (pour les premiers) :

10000 MAC - romain
10006 MAC - grec I
10007 MAC - cyrillique
10010 MAC - Roumanie
10017 MAC - Ukraine
10029 MAC - latin II
10079 MAC - islandais
10081 MAC - turc
10082 MAC - croate
1026 IBM EBCDIC - Turque (Latin-5)

Merci pour cette astuce toute simple que je ne connaissais pas (pas plus que les fichiers de ressources - je pensais qu'il fallait avoir l'édition professionnelle de VB, mais ce n'est pas le cas).
Pour répondre rapidement aux deux précédents commentaires (tardivement, mais ça peut servir à d'autres), voici la démarche à suivre pour créer le fichier de ressources :
- depuis VB6, aller dans le menu Compléments/Gestionnaire de compléments puis charger l'Editeur de ressource VB6 ;
- aller dans le menu Projet/Ajouter un nouveau Fichier de ressources. Lui donner un nom et un emplacement de stockage. Pour l'instant, il est vide et il apparaît dans l'Explorateur de projet, dossier Documents associés ;
- il suffit de double cliquer sur son nom pour lancer l'éditeur de ressources et ajouter les curseurs (ou autres objets nécessaires) à partir des icones de la barre de menu de l'éditeur.
Tout cela est bien sûr détaillé dans l'aide et on le trouve facilement en tapant LoadResPicture pour la recherche.

Excellent travail. Je voulais réaliser un petit générateur de formulaires en RTF, finalement, je l'ai fait en PDF en bénéficiant ainsi de la garantie de la restitution.
Evidemment, ce n'est pas très rapide, mais c'est incroyable ce qu'on peut réaliser en VB !
Une petite remarque : j'ai mis un certain nombre de variables d'entrée en Byval plutôt qu'en Byref. Cela permet d'utiliser, si on le souhaite, des variables entières plutôt que doubles dans le programme appelant.
Et en plus un suivi du projet est assuré depuis plusieurs années. Cela mérite vraiment 10/10

Le code de Zefri fonctionne bien si le chemin commence par une lettre de lecteur mais ce n'est pas le cas pour un chemin unicode du genre "\\Edmini\Share\" (disque dur distant par exemple - bon, je sais, on peut se connecter auparavant à un lecteur réseau pour déclarer une lettre de volume, mais j'aimerais faire sans)
Si quelqu'un a une solution...