It has recently been shown that submonolayer Pd on W(110) forms highly-ordered linear mesoscopic stripes at high temperatures. The stripes display an internal Pd superstructure with a nano-scale periodicity along the direction perpendicular to the periodicity of the stripes. The same type of superstructure is also observed in a wide range of temperatures below the stripe formation temperature. We present a combined experimental and theoretical study of this superstructure of Pd on W(110) and investigate its influence on the appearance of the linear mesoscopic stripes. By means of low-energy electron diffraction and low-energy-electron microscopy we show that it has a far more peculiar dependence on temperature and coverage than expected from a regular surface reconstruction. Using density-functional theory, we model the Pd superstructures as periodic vacancy-line type of configurations and investigate their energetics and elastic properties. From our calculated surface stresses and anisotropies for the vacancy-line type of configurations, and based on the continuum elasticity theory, we demonstrate quantitatively that the vacancy-line type of structure is a prerequisite for the formation of the linear mesoscopic stripes. Moreover, we show that the physics driving the formation of the internal superstructure is very similar to the one at play in forming the mesoscopic stripes themselves. ; Comment: 23 pages, 9 figures and 5 pages, 4 figures for the supplementary material