The /locate command doesn't actually locate the nearest object to you.

Example 1: nearest stronghold not found

Steps to reproduce:

1. Use the seed picker to generate "Coastal Village" in creative mode. You will spawn at 960,4.
2. From that location, the /locate stronghold command says the nearest stronghold is at 578,882 – about 950 blocks directly south-southwest.
3. However, there is another stronghold at 1460,546 – only 740 blocks southeast.

Update 3 May 2019: Additional steps:

1. Teleport to the nearer stronghold at 1460,546, or near to it.
2. /locate stronghold
3. The /locate command still returns the stronghold at 578,882, even though you're right on top of a different one.

The stronghold found by /locate is clearly farther away. It doesn't matter if you're directly on top of the one "invisible" to /locate, or if you move a short distance away from that spot.

Example 2: nearest monument not found

Steps to reproduce:

1. Use the seed picker to generate "Ocean Monument Ahead" in creative mode.
2. From the spawn point, the /locate monument command shows the nearest monument at -456,152 – over 850 blocks away
3. Teleport to the actual nearest monument, or near to it, at 280,120
4. Try /locate monument again. Even if you are directly over the monument at 280,120 (or near that spot), /locate still says the nearest one is at -456,152.
5. There's another nearby ocean monument directly north of the one you're on top of, at 312,-249. This one also isn't found. The /locate command still favors the far one, even though two other monuments are closer to you.

Is the command using taxicab distance rather than Euclidean distance? If so, that seems odd, because the whole point of /locate is to find the nearest structures. (Struck out, verified Euclidean distance is used, but /locate is failing to find a nearer structure even when I'm right over it; see comment below.)

This is possibly related to MC-138887 reported for Java Edition.