If this question concerns interpolating the projected coordinates from a printed map or display, the answer is easy: you can always linearly interpolate. This is because the world-to-display transformation is affine (and doesn't involve a projection at all). So I presume you are concerned about interpolating spherical coordinates; that is, lat/lon.
No projection is truly constant scale. In fact, the scale of non-conformal projections will vary with the orientation between two points on the map as well as from one location on the map to another.
Most scale deviations are quite small on large scale maps made with suitable projections. You run into problems only around the fringes of a projection's range of application (such as beyond +-3.5 degrees of longitude past the central meridian of a UTM zone or, for many projections, near the poles) or when the map displays an appreciable range of latitudes (more than a few degrees).
There definitely can be bad cases where linear interpolation across the map is far off. But this is not always the case for certain special interpolations. For example, in a north-up cylindrical projection, the middle vertical line of the map indeed splits the distances between the sides of the map. (But even with a cylindrical projection, vertical interpolation can fail. The Mercator is an extreme example.) So the direction of interpolation matters and how far you interpolate within the map also matters.