Definitions: Throughout let $(M,d)$ be a geodesic metric space [cf. p. 104 of EoD]* with $d$ the (strictly) intrinsic metric, i.e. for all $x,y \in M$, $d(x,y)$ equals the length of any minimizing geodesic segment joining $x$ and $y$.
(According to [p. 13 of EoD]*) given two points $x,y \in M$, the set $$I(x,y) := \{ z \in M: d(x,y) = d(x,z) + d(z,y) \} $$ is called the (closed) metric interval between $x$ and $y$.
A "minimizing geodesic segment", a.k.a. "(metric) geodesic", "minimizing geodesic" or "geodesic segment" or "global geodesic", between two points $x,y \in M$ is (the image of) an isometric embedding $\gamma$ of the closed interval $[0, d(x,y)] \subseteq {\mathbb{R}}$ into $M$, $\gamma:[0, d(x,y)] \to M$, with $ \gamma(0) = x, \gamma(d(x,y)) = y$. "Unit-speed parameterization", "length-minimizing curve", cf. $\dagger$.
Observation: Let two points $x,y \in M$ be given, as well as a minimizing geodesic segment $\mathcal{G} = \gamma([0,d(x,y)]) \subseteq M$ joining them. Then we know that for any $z \in \mathcal{G}$, $d(x,y) = d(x,z) + d(z,y)$, i.e. $\mathcal{G} \subseteq I(x,y)$, any minimizing geodesic segment connecting $x$ and $y$ is a subset of the closed metric interval between $x$ and $y$. (In other words, all minimizing geodesic segments are Menger-convex subsets [cf. p.15 of EoD]* of $M$.)
Question: When is the converse also true, so that the union of all minimizing geodesic segments between $x$ and $y$ is equal to the (closed) metric interval between $x$ and $y$?
Or in other words, under what conditions does $d(x,y)= d(x,z)+d(z,y)$ for a given point $z$ necessarily imply that $z$ belongs to the (image of) some minimizing geodesic segment joining $x$ and $y$?
Edit: I think this is equivalent to asking whether "Menger convexity" is equivalent to "geodesic convexity" for geodesic metric spaces. "Geodesic convexity" clearly implies "Menger convexity" but I am not sure why the converse would be true. /Edit
In case it simplifies the question or answer, possibly assume that $M$ is not only a geodesic metric space, but also a "uniquely geodesic" or "strongly geodesic" metric space, i.e. every two points are joined by a unique minimizing geodesic segment. (This would exclude e.g. the two-sphere.) I doubt it makes a difference though.
Note: Riemannian geometry tag added because I would also be interested in an answer for that special case of geodesic metric space, although the answer probably does not depend on that.
Comments/Clarifications/Notes:
* EoD = Encyclopedia of Distances, Michel Marie Deza and Elena Deza, Spring (2009) - Web archive link
$\dagger$ Think of the two-sphere, then given two non-antipodal points, there are two ("local") geodesics joining them -- then "minimizing geodesic segment" is meant to generalize the notion corresponding to the shorter of the two. In the case that two points are antipodal, then they are joined by two "minimizing geodesic segments", not just two ("local") geodesics.