Repository.check is overly zealous when checking stacked repositories. To be valid, a revision in a stacked repository needs to be streamable. It does not need all text versions in the revision to be present (just texts changed in that revision vs. the present parent inventories), but check fails a valid repository that satisfies that condition.
I've attached a patch to an existing test that demonstrates this. Run it with "./bzr selftest selftest -s bt.per_repository_reference.test_fetch test_sprout_from_smart_stacked_with_short_history.*2a"
The scenario, as should be fairly clear in the test, is a history with three revs, A,B,C. The stacked repo ought to only have rev C and inventories B,C. Check however fails trying to access a text that originates in A, and is unmodified in C (and B).
Also, note that check is happy when the fallbacks are available, but check ought to be clean even when they aren't.