I hope you bear with me here. It's difficult to explain this problem, especially so without direct reference to the specific domain.
I work on a component of a larger system which performs computationally expensive pre-processing in order that the "real-time" component can perform it's functions quickly. My product effectively creates a big lookup dataset for the main component to query.
My product computes the results of a finite set of "scenarios" (a few hundred thousand) any one of which may be performed by a customer. The component uses a k-shortest paths algorithm and a number of rules engines to consider each scenario and build up the lookups, operating on reference data that represents the problem domain.
For the scenarios that are very commonly performed by our customers the test cases are easy; the expected outcomes are easy to devise and assert acceptance tests. However, for the scenarios that are not "popular", the expected outcomes are difficult to establish and in any case their outcomes may be changed by changes to the reference data which are virtually impossible to predict. In other words, changes to the reference data changes the inputs to the shortest-path algorithm which in turn may change the output.
Creating acceptance tests for these unpopular cases is also tricky, because the business "doesn't know what it doesn't know", and so has no baseline against which it can be tested.
Whenever a tester comes back to me with a defect, 99.9% certainty it's because conditions in the reference data have changed, rather than because of any code changes. I therefore spend a load of time chasing defects that are "data issues". I think what confuses the situation is that the reference data is key to the functionality of the system, and the system without a specific set of reference data would produce no results that had any meaning to the business. I could create a set of "fake" reference data against which to test, but any assertion against this engineered reference data would be invalid in the real world.
I would be very interested to hear any perspectives on this especially from those who have encountered similar problems. I am anxious not to simply shrug my shoulders and reply "data issue" but get to the root of the problem and work out how to build and test this thing in a reliable, repeatable and valuable way.