Actually, you can get reproducible tests even with randomized tests, by setting the random seed (I always do that in e.g. Quickcheck). So this is really a moot point, not a good excuse not to do random testing (or not to use QuickCheck ;-P).
It would actually be really easy to package up seeded randomisation as a JUnit rule / extension. As far as i can tell, nobody has done that.