Yes but I think the apparent paradox is because there is an assumption that momentum has to reduce. That assumes that all that is changing is the speed of the photon. Surely, when an em wave travels through a medium, there is a constant interaction with the bulk of the medium and the photon is not just 'travelling through space with a different value for c'.
Start with the observed fact that the wavelength decreases and, rather than looking for a violation, think of how a photon could be making its way through the medium and it's not straightforward. It isn't as simple as saying it interacts with individual atoms - that would be an absorption / re-radiation process, like in a gas. So there doesn't have to be a conflict.
Also, there is the point that, on emerging from the other side of the medium, the photon will have the same energy and momentum as when it went in; it hasn't 'lost anything' as it would if the simplistic argument were applied.
If you think about it classically - a wave entering and emerging from a length of waveguide, you have the same sort of thing and you can explain the changes in wavelength in terms of distributed capacity and inductance (transmission line) and, probably also, forces on the waveguide at the entrance and exit, which would balance out.