It sounds like typical low-quality or dirty encoders. If they worked properly in the beginning, you might be able to restore proper function by taking them apart and cleaning them. Of course that's hit or miss, but I've had some luck doing that.
If you decide to replace them, you need to remove one and see what you'll need to order. There are basically two kinds of mechanical encoders - those with the same number of pulses as detents per revolution, and those with half as many pulses as detents. A "pulse" is one complete cycle of both switches. So the first kind always comes to rest at a detent with both switches open. The second kind can be either both-open or both-closed at a detent. You need to get the right kind because the firmware will be written for that kind of encoder.