Here's a walk-through in a toy model that might help with the visualization. We assume the Earth's orbit, the moon's orbit and the Earth's equator all lie in the same plane. This simplifies the visualization without doing any violence to the real situation.
Now let's deal with a waxing gibbous moon, halfway from first quarter to full.
We go to the north pole, and look at the moon and sun. Because of our simplifying assumptions, they're both lying on the horizon, with the moon 135 degrees away from the sun. Its fully illuminated side is facing the sun, terminator orthogonal to the horizon. We can draw a horizontal line on the sky, parallel to the horizon, connecting the sun and moon, and it, too, is orthogonal to the moon's terminator. This is the path light rays are travelling from sun to moon, and all seems consistent and normal.
Now go the equator. Find a point on the equator where the sun is sitting on the the western horizon. The gibbous moon is 45 degrees above the eastern horizon (ie, still 135 degrees from the sun). Its illuminated side is pointing towards the zenith: that is, it is facing upwards, despite the fact that the sun is on the horizon. The line we drew on the sky connecting the sun and moon now climbs vertically from the western horizon, crosses the zenith, and descends to the east until it hits the moon, still orthogonal to the moon's (now horizontal) terminator. After a bit of thought we can see that this is correct: the sun's rays are shining far over our heads to illuminate the moon, so we can see a little way "under" the illuminated face to the shadowed side.
Now, picture a line of observers strung out along the line of longitude that connects our equatorial observing point to the north pole. For each of them the sun is going to be on the horizon. For each of them, the moon's illuminated face is going to be pointing in some direction intermediate between straight up (the equatorial situation) and horizontally (the polar situation). So every single observer in those mid-latitudes will see the illuminated side of the moon tilted upwards to some degree, despite the fact that all of them see the sun on the western horizon. Wait a few moments for the sun to set, and all will have a view similar to the one described in the OP.
For these observers, the line we drew in the sky now appears to curve upwards from the sun's position, reach a high point due south, and then curve down to meet the moon orthogonal to its terminator.
But it's the same line. We thought it was straight when it was parallel to the horizon, and we convinced ourselves it was straight when it ran vertically. But our brain is unhappy with the convergence that is an inevitable part of seeing long parallel lines in a perspective that covers a big angular arc. A long line that converges on both horizons (as sun rays at sunset do), seems like it must have a curve in it somewhere. So in these intermediate latitudes, it seems like we ought to be able to draw a straighter line between moon and sun, undercutting the line in the sky we previously agreed to be straight!
But imagine (for the moment) you could do that. So draw a new line that undercuts our original line and looks straighter. Now head back to the pole, so that our original line is running along the horizon, connecting the sun and moon. Where is our new line? It must be leaving the sun, curving below the horizon and then up again to hit the moon! So it can't be straighter.

So it's all just a trick of perspective. If, at some intermediate latitude, you could do an experiment in which you held your head dead steady, and stretched a piece of string from your right thumb (covering the sun on the horizon) to your left thumb (covering the gibbous moon high in the sky), you'd find the string did seem to pass higher than your head and then descend towards your view of the moon, meeting it at right angles to its terminator.

Grant Hutchison