I only played Still Life and that is indeed just a linear adventure game and I didn't find the story to be that good (to drift off-topic for a bit, in adventure games, I could recommend the Syberia games and The Longest Journey for simply having an excellent storyline).
Anyway, the trial and error model... I certainly agree that it can be implemented in a frustrating way, requiring countless replays of a memorized sequence of actions.
After the initial exploration of Date Ariane I do recognize this process. At first you try some random stuff, see that the game has a lot to offer, but to really 'achieve' something you have to do better than random or even acting on intuition. Eventually you begin to memorize sequences because in the end that is what it takes to be succesful and see everything the game offers. A step even further is when you start to understand the game mechanics and you'll just learn the sequences that rack up 'nice'-points and 'drunk'-points and then go for the sex-scene (Chaotics games also spring to mind).
At this point I could take a detour to the "Women aren't vending machines" post ExLibris mentioned. The final step (understanding the game mechanics) is very related to this:
"This design approach is extremely simplistic and perpetuates the commodity model of sex—the player wants sex, they go through certain motions, and they are "rewarded" with what they wanted (like a vending machine)"
The post was an interesting read, by the way.
Back to trial and error. Be it that it can be used in a way that is frustrating, that doesn't mean it is a frustrating principle at its core.
Right now I can think of two games that use the principle a lot better: Masq and School Dreams 3.
In Masq I've never really been tempted to go for the combinatoric way (simply try all possible actions one by one). My first theory to this is that you only get 10 tries (without paying at least, or putting effort in registering multiple times maybe), so it's impossible to try everything. But I don't think that does the game justice. For one, there is the size. In the 5 episodes you take a lot of choices, but it remains relatively obscure which ones really influence the events (knowing the existence of a certain scene I've tried to work towards it, but that turned out to be incredibly hard). As a closing argument you could say it is an interactive story and not really a 'game', so choices don't need to have a result that is predictable to some degree. Rather, a choice resulting in a plot twist can be a good storytelling device. On top of that, almost none of the choices lead to an end, the story always progresses. So there's a lot of trial and little error.
Moving on to School Dreams 3. While it's a text adventure in its core I'd say it has a lot of similarities with the dating games. I do think that SD3 feels a lot more natural (is it just that it's well-written, or does that come from the freedom of interaction with the world?). As an example, my own first experiences with the game. Not knowing what to expect I get thrown into a world where I'm told I have a girlfriend, Becky. My response to that was pretty much what I'd do in real life: stay faithful. I play through the game and might have gotten the Becky-end, I can't remember. On the 2nd try I know of the existence of Molly, which I want to explore. Pre-emptively (Groundhog Day, anyone?) I try to see if I can break up with Becky directly to free myself from that bond. For me this would be a natural interaction if there was a more appealing romantic interest. Of course this is where I'm no longer able to project myself onto the character: I can't break up immediately. After all the creator can not code in every possible action (let alone something as pre-emptive as what I tried). Still, it remained to feel quite natural. One other thing that helps is that as the player you are hardly forced into situations where you do not choose to be.
But about trial and error: it may seem weird to apply that to a text adventure with little clear choices. A great aspect of it is that we make choices that are less apparent than a multiple choice question with actions (and the order in which you take them is not necessarily important). As such, I believe it becomes less likely that you memorize every choice explicitely.
SD3 relates to Masq as well, because the story has no endings in the middle, all choices culminate to the birthday party (which is in effect a measure of your success). Again: a lot of trial and little error.
On a sidenote, I regret finding out about the 'status' command, because it directly reveals the relationship status of Molly and Becky. The game would've been better without it in my opinion.
On a 2nd sidenote, strangely enough, in my mind it seems SD3 applies less of the 'vending machine' model (which I find strange in a world where every girl is essentially a slut). For example on the first date with Molly you can do all nice actions you want, she won't put out much.
A lot of words, but to sum up I think I should draw a logical conclusion that in my mind a 'good' trial and error game is one that avoids having endings 'in the middle'. I would call it having a delayed response: only at the end you fully know how well you did. I realize though that this is hard to do in a game that only covers a single date.
For direct responses ("you turn left, you die!") I would think a limited undo option is a more useful choice than a save system. Not only does it allow faster exploration in a limited area of the story, but because you only turn back one or two steps you remain immersed by the story, where with loading a savegame you are likely to have forgotten the context of what leads up to it.
I know I've used 'undo' in SD3 quite a bit, but never to go back more than a few choices (a fundamental change in strategy was better served with a complete replay). Similarly I've used 'back' on Date Ariane (especially the photoshoot at the lookout point comes to mind: lots of 'instant failure' choices, too many to justify replaying up to that point over and over).