Let $(M, g)$ be a Riemannian manifold, not necessarily complete. Let $x$ be a point in $M$, and let $r>0$ be such that the exponential map $\operatorname{exp}_x$ is defined on an open ball $B=B(0,r)\subseteq T_xM$. That is, all geodesics from $x$ exist to distance $r$.
If $y$ is a point in $M$ whose Riemannian distance from $x$ is less than $r$, does there necessarily exist a minimizing geodesic from $x$ to $y$?
This is indeed the case. The basic reason is that within the domain of the exponential map, there are no issues of completeness (the minimizing geodesic needs to stay within this set.) As such, minimizing curves are indeed geodesics. I don't know of an elegant proof for this, but it's possible to just brute force the issue.
For a brute force approach, we want to find a complete manifold $\bar Q$ whose Riemannian metric coincides with that of $M$ on an open ball of $x$. From there, we can use the theory for complete manifolds to finish the argument.
Since $y$ is in the image of the exponential map, we have that $y = \exp_x(s\cdot \mathbf{v})$ for $\|\mathbf{v}\|=1$ and $s<r$. Pick $ q$ with $s< q<r$ and consider the set $U_q=\exp_x(B(0,q))$. This is an compact subset of $M$ with Lipschitz boundary.
As such, we can find an open domain $Q$ so that $$\exp_x(B(0,s)) \subset Q \subset U_q$$ and $Q$ has smooth boundary. Now, each of the $j$ boundary components $\partial Q_j$ are sub-manifolds, so we can attach cylinders $(\partial Q_j) \times [0,\infty)$ to $Q$ so that the resulting space $\bar Q$ is complete. We can do this attachment smoothly so that $\bar Q$ is a complete Riemannian manifold.
By our construction, there is a natural inclusion $ i:\exp_x(B(0,s)) \to \bar Q$. Via the triangle inequality, the minimal curve from $i(x)$ to $i(y)$ is completely contained in the image of $i$ and the Riemmanian metric of $M$ is the same as the Riemannian metric of $\bar Q$ on the set $\exp_x(B(0,s))$.
Therefore, if $\gamma$ is the minimizing curve from $x$ to $y$, then $i(\gamma)$ is the minimizing curve from $i(x)$ to $i(y)$ (and vice-versa). Since $\bar Q$ is complete and length minimizing curves in complete manifolds are geodesics, the curve $i(\gamma)$ is a geodesic. As such, the minimizing curve from $x$ to $y$ is also a geodesic.
Edit to address a question:
Macbeth asked how we know that $y$ is in the image of the exponential map, so I'm including an edit to address this question. This is only a sketch because it's really hard to give a clear proof without drawing a picture. As before, this a brute force argument that doesn't do the geometry justice. Intuitively, geodesics travel away from a point as fast as possible, so there is no way for a curve of the same length to be a further distance away.
Suppose that there were a point $y$ with $d(x,y)<r$ and $y$ was not in the image of the exponential map. Then there we can construct a sequence of points $y_i$ so that all of the points $y_i$ are not in the image of the exponential map and so that $d(x,y_i)$ decreases to the infimum of distances for which the exponential map is not surjective. We can extract a convergent subsequence and consider the limit point $y_\infty$. Since all points $x'$ with $d(x,x') < d(x,y_\infty)$ can be joined to $x$ via a geodesic, the path minimizing the distance from $x$ to $y_\infty$ is composed of at most two geodesic segments (there's something left to prove here). By applying the triangle inequality and taking a sequence of points on the second segment of the piecewise geodesic curve, this actually shows that there is a unique geodesic from $x$ to $y_\infty$.
To get a genuine contradiction, consider $m$ large so that $y_m$ close enough to $y_\infty$ so that we can connect $y_m$ to $y_\infty$ via a single geodesic. Then there is a two geodesic path from $x$ to $y_m$, but not a single geodesic path from $x$ to $y_m$, by assumption. To get a contradiction, we will find a sequence of piecewise geodesic paths which converge to a geodesic from $y_m$ to $x$.
To start this procedure, find a geodesic connecting $y_m$ to a point $x_1$ on the geodesic connecting $x$ to $y_\infty$. The geodesic connecting $y_m$ to $x_1$ followed by the geodesic connecting $x_1$ to $x$ is shorter than our original segments via the triangle inequality. Then, find a point $y'_1$ of distance $d(x,y_\infty)$ from $x$ on the geodesic segment from $y_m$ to $x_1$. The geodesic connecting $y_m$ to $y'_1$ followed by the geodesic connecting $y'_1$ to $x$ is shorter than the previous geodesic segments. Repeating this to obtain points $x_i$ and $y'_i$, we find a sequence of such paths. I definitely recommend drawing a picture here, because it's hard to follow without one.
If one does this procedure in a reasonable way, then the sequence of paths will converge to a geodesic. A priori, it's only piecewise geodesic, but the direction on either side of $y'_\infty$ will be equal if you do this reasonably. As such, there is a geodesic from $x$ to $y_m$ whose length is less than $r$, which is a contradiction.
I am writing my reformulation of Gabe's argument here (community wiki), in case it is useful to others!
Let $\Sigma$ be the set of real numbers $t\in[0,r)$ such that for all $y$ with $d(x,y)\leq t$, there is a minimizing geodesic from $x$ to $y$. Clearly $\Sigma$ contains $0$ and is connected. We will show it is closed and open, which implies $\Sigma=[0,r)$.
Lemma. If $t\in\overline{\Sigma}$, then for any point $y$ with $d(x,y)\geq t$, there exists a vector $v\in T_xM$ with $|v|=t$, $d(x,\exp_x(v))=t$, and $d(\exp_x(v),y)=d(x,y)-t$.
Proof. Let $(t_n)$ be a sequence in $\Sigma$ tending to $t$. For each $n$ there exists a point $y_n$ such that $d(x,y_n)=t_n$ and $d(x,y)-t_n\leq d(y_n,y)<d(x,y)-t_n+\tfrac{1}{n}$. Since $t_n\in\Sigma$, there exists a minimizing geodesic from $x$ to $y_n$, hence a vector $v_n\in T_xM$ such that $|v_n|=t_n$ and $\exp_x(v_n)=y_n$. Passing to a subsequence, we may assume $(v_n)$ converges to some $v\in T_xM$ with $|v|=t$. This $v$ has the desired property.
Claim 1: $\Sigma$ is closed. (This works in any Riemannian manifold.)
Proof. Suppose that $[0,t)\subseteq\Sigma$. Let $y$ be a point with $d(x,y)=t$. By the Lemma, there exists a vector $v\in T_xM$ with $|v|=t$, $d(x,\exp_x(v))=t$, and $d(\exp_x(v),y)=0$. Thus $\exp_x(v)=y$. So the exponential map in direction $v$ is a minimizing geodesic from $x$ to $y$. We conclude $t\in\Sigma$.
Claim 2: $\Sigma$ is open.
Proof. Suppose that $t\in\Sigma$. Then the closed Riemannian ball $B:=\{\overline{y}:d(x,\overline{y})\leq t\}$ is equal to the image of the closed ball $\overline{B(0,t)}\subseteq T_xM$ under $\operatorname{exp}_x$, and therefore is compact. (This is where we use the hypothesis that $\operatorname{exp}_x$ is defined throughout $B(0,r)\subseteq T_xM$.) There therefore exists $\epsilon>0$, such that for all $\overline{y}\in B$, there are geodesic co-ordinates about $\overline{y}$ to radius $\epsilon$.
Let $y$ be a point with $t<d(x,y)<t+\epsilon$. By the Lemma, there exists a vector $v\in T_xM$ with $|v|=t$, such that, letting $\overline{y}:=\exp_x(v)$, we have $d(x,\overline{y})=t$, and $d(\overline{y},y)=d(x,y)-t<\epsilon$.
So, using the geodesic co-ordinates about $\overline{y}$, we can construct a minimizing geodesic from $\overline{y}$ to $y$. Since $d(x,y)=d(x,\overline{y})+d(\overline{y},y)$, and both these distances are achieved by minimizing geodesics, the distance from $x$ to $y$ is also achieved, necessarily by a minimizing geodesic. We conclude that $[t,t+\epsilon)\subseteq \Sigma$.
I can answer the question under the additional assumption that $exp_x$ is a diffeomorphism on $B(0, r) \subseteq T_x M$, that is, if its image is a geodesic ball. All you need to do then is to invoke the following standard
Lemma. In the notation as above, let $U = exp_x (B(0, r)) \subseteq M$, and let $y \in U$. Then (up to reparametrization) the radial geodesic from $x$ to $y$ is minimizing (in fact, it is the unique minimizing curve from $x$ to $y$ in $M$, but we do not need that).
Reference: Proposition 6.10, John M. Lee, Riemannian Manifolds: An Introduction to Curvature, Springer (1997).
Having this said, we need only to show that $d(x,y) < r$ implies $y \in U$. Assume the converse: $y \notin U$. Let $\gamma \colon [a, b] \to M$ be a piecewise-smooth curve from $x$ to $y$ of length less than $r$. Let $c = \sup\{t \in [a, b] \, \colon \; \gamma(t) \in U\}$. On can easily see (from the lemma) that $d(x, \gamma(c)) \geqslant r$, which leads to a contradiction.
Let $\overline{M}$ be the completion of $M$ as a metric space. For any $x, y \in M$, there exists a length-minimizing curve $c \subset \overline{M}$ from $x$ to $y$. Since $c \cap M$ is locally length-minimizing, it must consist of geodesic segments.
Assume $B = \exp_x B(0,r) \subset M$ and $d(x,y) < r$. If $y \notin B$, then the geodesic segment of $c$ that starts at $x$ must hit the boundary of $B$ and therefore has length at least $r$, which contradicts the length-minimizing property of $c$. It follows that $y \in B$ and $c$ is a length-minimizing geodesic in $B$ that connects $x$ to $y$.
