"Unsolvable" is strong. My take is that these problems stem inevitably from approaching the goal ass-backwards.
You're trying to force a particular testing framework on people who don't care about frameworks, supposedly in the name of "better communication". There's no reason to expect that to work.
The way I've advocated doing it, for years now, is to first sit with the people in question, discover how they communicate about business goals that the programming effort is expected to assist, formalize their notation as little as you can get away with and use that for acceptance testing.
This should be a process of active listening, not passive recording. The client should be gently nudged away from speaking in solution-terms, for instance.