Young's modulus is generally pressure dependent. (Tabulated values are assumed to be at standard atmospheric pressure unless otherwise stated.)
Here's a simple way to think about it: Stretching a material in one direction tends to increase its volume (by a factor of $1-2\nu$ for isotropic materials, where $\nu$ is Poisson's ratio that never exceeds 1/2 in stable materials). Under tremendous pressures, for example, it wouldn't make sense to obtain this volume increase for free; one has to pull harder to exert the greater work needed to expand the material.
At a more sophisticated level, the reason Young's modulus depends on pressure is that uniaxial stress can be decoupled into a so-called deviatoric stress state and a so-called dilatational stress state.
The former stress state can be thought of as a more sophisticated 3D version of simple shear, although its tensor representation can contain nonshear components. More importantly, deviatoric stresses tend to change the shape of objects, maintaining their volume. For this reason, the relationship between deviatoric stresses and strains isn't really dependent on the surrounding pressure.
The latter stress state is strongly coupled to pressure, though; in fact, hydrostatic pressure is just a negative dilatational stress. Dilational stresses tend to change the size of objects. Materials get stiffer as you squeeze them, and so qualitatively, adding hydrostatic pressure can be expected to alter Young's modulus.
Quantitatively, for isotropic materials, Young's modulus $E$ equals $\frac{9KG}{3K+G}$, where $K$ is the bulk modulus and $G$ is the shear modulus. The former is expected to exhibit positive pressure dependence, and the latter is not expected to be strongly pressure dependent (with zero dependence predicted under the idealization of a deviatoric vs. dilatational dichotomy as discussed above). Thus, we expect a pressure dependence—always positive—of $$\frac{dE}{dP}=\frac{9G^2}{(3K+G)^2}\frac{dK}{dP}.$$ The bulk modulus dependence on pressure $\frac{dK}{dP}$ can be found in the literature for many materials.
To answer your last question, yes, varying depth-dependent pressure does complicate the analysis. Except for simple geometries, you'd likely have to analyze the stress state numerically (using finite element analysis, for instance).
Does this all make sense?