The answer is **no**. 

### Define the manifold

Let $f$ be a smooth function on $\mathbb{R}$ satisfying

1. $f(r) = |r|$ for $|r| > 3$
2. $f(r) > 0$
3. $f''(r) \geq 0$. 

The corresponding warped product metric on $\mathbb{R}^2$

$$ \mathrm{d}s^2 = \mathrm{d}r^2 + f(r)^2 \mathrm{d}\theta^2 $$

is complete and has non-positive curvature. The exterior regions $|r| > 3$  are flat. It is in fact the simply connected cover of a corresponding warped metric on $\mathbb{R}\times\mathbb{S}^1$, which when $|r| > 3$ are two copies of the Euclidean plane with a ball removed. 

Since geodesics (lines) in the Euclidean plane are confined to a half plane, we know that geodesics satisfying $|r(\gamma)| > 3$ must have bounded $\theta$ within some $[\theta_0, \theta_0+\pi]$. In other words, for a lot of what we are going to say we can just work in the quotient picture, without worrying too much about the lift to upstairs. 

### Counterexample

In the quotient picture fix, in rectangular coordinates on $\mathbb{R}^2 \setminus B_3(0)$ a point $(x,y)$ in the first quadrant, such that

1. $x> y > 3$
2. the line $\tilde{\gamma}: t\mapsto (x-t/\sqrt{2}, y-t/\sqrt{2})$ does not enter the ball of radius 3. 

Let $o = (x,y)$ (or rather its lift to our manifold defined above), and $a   = (x,0)$, $b = (y,0)$. 

Notice that $\tilde{\gamma}$ is geodesic. Note also that we don't have to worry about the quotient/lift since $L_a, L_b$ and $\tilde{\gamma}$ all avoid the "cut" at $\{x = y \wedge x,y < 0\}$. 

Note further that for some $\epsilon$ time that $\tilde{\gamma}(t)|_{t\in (-\epsilon,\epsilon)} = m(t)$. 

Note also that $\tilde{\gamma}(t)$ always stay on the "$L_a$ side" of the "hole"

But this does not hold for all times: once the geodesic segment joining $L_a(t)$ to $L_b(t)$ starts to enter the ball of radius 3, its midpoint would start to deviate from $\tilde{\gamma}$, and move closer toward $L_b(t)$. 

This is easiest to see when $t$ is very very large. When $t$ is very very large, on the original manifold, the geodesic connecting $L_b(t)$ to $L_a(t)$ must first go into the hole, which requires travelling distance approximately $t - y +  O(1/t)$, and exit the hole, and reach $L_a(t)$, traveling another distance that is approximately $t-x + O(1/t)$. The distance traveled in the hole is $\leq 6\pi$. So asymptotically the midpoint $m(t)$ remains in fact in a compact region of our manifold. If initially $y$ is much smaller compared to $x$ (in the sense that $x-y > 6\pi$), in fact we expect $m(t)$ to appear "on the other side of the hole" eventually. 

Since $m(t)$ and $\tilde{\gamma}(t)$ coincide for some time interval, but their image do not coincide globally, we conclude that $m(t)$ cannot be always a local geodesic.