avevo già provato questa soluzione ma è lenta lo stesso.. per intederci:

+----------+
| rand_row |
+----------+
| 40828799 |
+----------+
1 row in set (57.07 sec)

Aggiungendo una WHERE impiega:
1 row in set (1 min 2.17 sec)

Improponibile..

Comunque, se potesse aiutare, il server MySql è un AMD Athlon Xp 2000+ con 1gb di ddram 400mhz, disco da 80gb 7200rpm.. fra poco in raid 0.

La versione di MySql:
4.1.11-Debian_4sarge2-log

Non so su cosa intervenire.. anche perchè non posso splittare la tabella..