Thanks @lossyrob and @matthewhanson for the advice that seems to be a sensible choice. Most probably I'll really go the route via rasterization -> vectorization -> simplification on my datasets as well.
So for the balancing act, I see that it is neither desireable to make the boundaries too large (users get too many unusable results) nor to make them too small (users get too few results). And generally having as few points as possible is good. If I do simplification, I'll either have to define some tolerance in terms of distance or I need to define a maximum amount of points which may be returned or both. Are there any established good number for that? I could imagine rules like (but maybe there are more options):
Each of those may have their problems and maybe there are no good general advice. But as a good choice not only depends on the dataset creators capabilities but also on the user of the dataset, I've the feeling that a general guideline could be helpful.