Credo che il fatto sia dovuto al tipo di variabile utilizzata per l'indice della listbox, che mi pare sia di tipo integer.
Se superi un tot di elementi all'interno della lista, mandi in overflow la variabile dell'indice, è normale.

Credo che l'unica cosa che tu possa fare, è crearti una listbox personalizzata in cui la variabile per l'indice la metti di tipo long invece che integer.

Spero che usi VB.NET, altrimenti il lavoro non sarà facile.