randomizando grandes conjuntos de dados

Estou tentando encontrar uma maneira de obter uma seleção aleatória de um grande conjunto de dados.

Esperamos que o conjunto cresça para ~ 500K registros, por isso é importante encontrar uma maneira de manter um bom desempenho enquanto o conjunto cresce.

Eu tentei uma técnica de:http://forums.mysql.com/read.php?24,163940,262235#msg-262235 Mas não é exatamente aleatório e não funciona bem com umLIMIT , você nem sempre obtém o número de registros que deseja.

Então eu pensei que, como o PK é auto_increment, eu apenas gero uma lista de IDs aleatórios e uso uma cláusula IN para selecionar as linhas que eu quero. O problema dessa abordagem é que, às vezes, eu preciso de um conjunto aleatório de dados com registros com status spefic, um status encontrado em no máximo 5% do conjunto total. Para fazer esse trabalho, eu primeiro precisaria descobrir quais IDs eupode use esse status específico, para que também não funcione.

Estou usando o mysql 5.1.46, mecanismo de armazenamento MyISAM.
Pode ser importante saber que a consulta para selecionar as linhas aleatórias será executada com muita frequência e a tabela da qual está selecionando é anexada com frequência.

Qualquer ajuda seria muito apreciada!