The reason your expectations of kinetic energy loss are violated is because you picked a non-inertial reference frame.
In fact, you didn't notice, but based on your assumptions, momentum isn't even conserved.
Let's look more closely at your first equation:
$$m_e * 0 + m_i v_i = m_e * 0 + m_f v_f$$
Let's say the ball's mass is 5 kg. If the ball is falling down towards the ground, the initial velocity before the collision should be negative (assuming we have adopted a coordinate system where "up" is positive). Let's say the ball was moving at 10 m/s. Here is our equation so far:
$$m_e * 0 + (5 kg) (-10 m/s) = m_e * 0 + (5 kg) v_f$$
Let's simplify, given your assumption that the Earth doesn't move:
$$(5 kg) (-10 m/s) = (5 kg) v_f$$
Which gives us
$$ v_f = -10 m/s $$
Whaaa? The final velocity is negative? That means . . . after this "collision", the ball is still falling downward at the same speed! If we assume, as you did, that the velocity was positive, then the momentum of the system can't be conserved! Clearly, something is wrong here.
Here's the trouble: You began in the reference frame of the Earth. Once the ball hit the Earth, the Earth's reference frame is no longer inertial! You either have to introduce a fictitious force on the ball to account for the fact that the Earth accelerated (a tiny bit, yes, but an important tiny bit), or you need to find an inertial reference frame.
So, Let's pick the frame of reference in which the Earth starts out at rest. When the Earth moves, we'll let our frame of reference stay where it is, so as to allow it to remain inertial:
$$m_e * 0 + (5 kg) (-10 m/s) = m_e * v_{e, f} + (5 kg) v_f$$
$$-50 kg m/s = m_e * v_{e, f} + (5 kg) v_f$$
NOW we can introduce a coefficient of elasticity and demand that energy be either conserved or not, and find the final velocity of the Earth and the ball as they rebound from each other.
Note that although $v_{e, f}$ will be incredibly tiny, due to the enormous mass of the Earth $m_e$, the final momentum of the Earth will be non-negligible - in fact, the final momentum of the Earth must be comparable to the final momentum of the ball in order for momentum to be conserved!
So, to sum up: You picked a non-inertial reference frame, and didn't account for it, so your reliance on the laws of physics was betrayed.
Momentum, energy, angular momentum, and charge are conserved locally, globally, and universally. One must remember that conservation locally (within a defined system) does not mean constancy. Constancy occurs only when the system is closed/isolated from the rest of the universe.
Conservation means that these quantities cannot spontaneously change. Let's consider momentum: the momentum of a system at a later time must equal the momentum at an earlier time plus the sum of the impulses applied to a system. The impluses in this sum could be adding or removing momentum from the system, but never creating nor destroying momentum:
$$\vec{p}_{later}=\vec{p}_{before}+\Sigma\vec{J}_{during}.$$
For an isolated collision, without outside influence, $\vec{J}_{during}=0$, and $\vec{p}_{later}=\vec{p}_{before}$.
For the energy: $E_{later}=E_{before}+W+Q+\mathrm{radiation}$
For angular momentum: $\vec{L}_{later}=\vec{L}_{before}+\Sigma\vec{\Gamma}_{outside}$ ($\Gamma$ is torque on system)
For charge: $ Q_{later}=Q_{before}+\int I\;\mathrm{d}t$
In the case of kinetic energy, it is not universally conserved. It can appear and disappear as energy is transformed to different manifestations:heat internal energy, gravitational, electromagnetic, nuclear, all of which are energy. The total energy is conserved in a system (not necessarily constant), with the transfer agent being work/radiation/heat. The elastic collision is defined to be one in which the kinetic energy of the system remains constant.
Note that if you define a single object as the system of interest, neither the momentum nor the kinetic energy will remain constant during a collision with another object or while it falls in a gravitational field, but the momentum will be conserved (the object is subjected to impluses) and the energy of the object is conserved (outside forces do work).
Bottom line: Define a system, look for transfers of momentum (impulse), energy (work, etc), angular momentum (torque), and charge (current) into or out of the system. Then see if any of those conserved properties are also constant for your situation.
EDIT - Response to OP specific questions:
My specific question (in addition to the above) is: If in a collision
there is a coefficient of restitution BELOW 1, doesn't that mean that
the collision is INELASTIC? YES OR NO!
Yes. One may also call it partially elastic. If the coefficient of restitution is zero (0), the collision is completely inelastic.
And if that means that the collision IS INELASTIC, is it correct to
use AT THE SAME TIME momentum conservation equation? YES OR NO!
Yes. Momentum is conserved in all collisions and explosions. And sometimes it might even be constant for short periods of time.
Best Answer
Yes, kinetic energy is always lost in an inelastic collision. This is by definition. A collision where kinetic energy is conserved is called "elastic". "Inelastic" means "not elastic", so kinetic energy is not conserved, by definition.
My guess is that the author of that sentence in Wikipedia was using the word "may" to express contrast between two ideas, not to express contingency. The sentence is roughly equivalent to
An everyday example of this use of the word "may" would be
The speaker doesn't mean that it is uncertain that Carl said "thank you" - Carl did say "thank you". Instead, the word "may" is being used to introduce contrast, in this case contrast between Carl's words and his intent. In the sentence you quoted, the contrast is between kinetic energy not being conserved and momentum being conserved.
Of course, I did not write the Wikipedia article and cannot say with certainty that this is the intended interpretation.