[HenrikAI]

Något i stil med detta, kanske:

SELECT col1, col2, ..., -RAND()*UNIX_TIMESTAMP(PostDate) AS random_value
FROM TestTable
ORDER BY random_value ASC

Vet inte hur bra det är rent prestandamässigt dock.

Annars kan du lösa det med lite kod i ditt favoritspråk. Ta ut ett slumptal, t.ex. mellan 2000 och 2013 (eller vad du nu har för årtal på raderna i databasen), och kör något i stil med:

SELECT col1, col2, ...
FROM TestTable
WHERE YEAR(PostDate) <= $slumptal
ORDER BY RAND()