Se ho capito bene esegui una query per ogni record che vuoi visualizzare + una query (count) per sapere il numero totale dei record. E' così?
In questo caso la cosa strana non è che "a volte è lentissimo" ma che "a volte è velocissimo"!
Prova a eseguire una sola query sul db (usi una sola connessione, nessuno sforzo per il pooling, ecc.), quindi pagina il recordset (ci sono decine di esempi che ti spiegano come fare) e usa la proprietà RecordCount per sapere il totale dei risultati (attenzione al cursore che usi per l'apertura del recordset!).
Se fai già così... prova a postare il codice, specificando che db usi.
Ciao
m.casati