I notice that fscheck's conditional expressions aren't quite lazy enough. For example, say I have
let prop_foo = forAll (Gen.Int) (fun a -> false ==> prop (printf "foo\n"; true))
quickCheck prop_foo will print foo 100 times before saying that the arguments were exhausted. But if the left-hand side of ==> is false, the right-hand side shouldn't be evaluated at all!
Haskell gets around this problem by its implicit laziness (to say nothing of its referential transparency). QCheck for sml requires the arguments of ==> to be functions, and achieves its laziness that way.
Actually QCheck for sml has a slightly different design from fscheck, but the authors seem to have gotten around some of the limitations you've run into. Have you looked at it?
galen