We present a theory of neutrino oscillations in a dense medium which goes beyond the effective matter potential used in the description of the MSW effect. We show how the purity of the neutrino state is degraded by neutrino interactions with the environment and how neutrino--matter interactions can be a source of decoherence. We present new oscillation formulae for neutrinos interacting with leptons and carry out a numerical analysis which exhibits deviations from the MSW formulae for propagation through the Earth of ultra-high energy neutrinos. In particular, we show that at high density and/or high neutrino energy, the vanishing transition probabilities derived for MSW effect, are non zero when the scattering is taken into account.