We discuss a novel effect in neutrinoless double beta (0{ u}{beta}{beta}) decay related with the fact that its underlying mechanisms take place in the nuclear matter environment. We study the neutrino exchange mechanism and demonstrate the possible impact of nuclear medium via Lepton Number Violating (LNV) 4-fermion interactions of neutrino with quarks from decaying nucleus. The net effect of these interactions is generation of an effective in-medium Majorana neutrino mass matrix. The enhanced rate of the 0{ u}{beta}{beta}-decay can lead to the apparent incompatibility of observations of the 0{ u}{beta}{beta}-decay with the value of the neutrino mass determined or restricted by the {beta}-decay and cosmological data. The effective neutrino masses and mixing are calculated for the complete set of the relevant 4-fermion neutrino-quark operators. Using experimental data on the 0{ u}{beta}{beta}-decay in combination with the {beta}-decay and cosmological data we evaluate the characteristic scales of the LNV operators: {Lambda} > 2.4 TeV.