Você poderia resolver isso com alguma desnormalização:

• Crie uma tabela secundária que contenha as mesmas pkeys e status que sua tabela de dados
• Adicione e preencha uma coluna de grupo de status que será um tipo de subchave que você numera automaticamente (incremento automático baseado em 1 relativo a um único status)

Quando você não precisa filtrar, você pode gerar rand #s no pkey como você mencionou acima. Quando você precisar filtrar, gere rands em relação às StatusPkeys do status específico em que você está interessado.

Existem várias maneiras de construir esta tabela. Você pode ter um procedimento executado em um intervalo ou pode fazê-lo ao vivo. O último seria um impacto no desempenho, já que o cálculo do StatusPkey pode ficar caro.