We present the results of a study utilising ultra-deep, rest-frame UV, spectroscopy to quantify the relationship between stellar mass and stellar metallicity for 681 star-forming galaxies at $2.5<z<5.0$ ($langle z rangle = 3.5 pm 0.6$) drawn from the VANDELS survey. Via a comparison with high-resolution stellar population models, we determine stellar metallicities for a set of composite spectra formed from subsamples selected by mass and redshift. Across the stellar mass range $8.5 < mathrm{log}(langle M_{ast} rangle/rm{M}_{odot}) < 10.2$ we find a strong correlation between stellar metallicity and stellar mass, with stellar metallicity monotonically increasing from $Z_{ast}/mathrm{Z}_{odot} < 0.09$ at $langle M_{ast} rangle = 3.2 times 10^{8} rm{M}_{odot}$ to $Z_{ast}/Z_{odot} = 0.27$ at $langle M_{ast} rangle = 1.7 times 10^{10} rm{M}_{odot}$. In contrast, at a given stellar mass, we find no evidence for significant metallicity evolution across the redshift range of our sample. However, comparing our results to the $z=0$ stellar mass-metallicity relation, we find that the $langle z rangle = 3.5$ relation is consistent with being shifted to lower metallicities by $simeq 0.6$ dex. Contrasting our derived stellar metallicities with estimates of gas-phase metallicities at similar redshifts, we find evidence for enhanced $rm{O}/rm{Fe}$ ratios of the order (O/Fe) $gtrsim 1.8$ $times$ (O/Fe)$_{odot}$. Finally, by comparing our results to simulation predictions, we find that the $langle z rangle = 3.5$ stellar mass-metallicity relation is consistent with current predictions for how outflow strength scales with galaxy mass. This conclusion is supported by an analysis of analytic models, and suggests that the mass loading parameter ($eta=dot{M}_{mathrm{outflow}}/M_{ast}$) scales as $eta propto M_{ast}^{beta}$ with $beta simeq -0.4$.