It seems like if you know that it will produce unpredictable results around 20% of the time, you could determine the number of tests necessary to verify that boundary.

I guess I would suggest trying to encapsulate the fuzzy bit into a function that can be swapped out with a less fuzzy (more predictable) function during testing. Then, test the core fuzzy bit separately using sample sizes that are statistically significant.

<tiny>Geeze, I sound like one of my old professers.</tiny>