You are right - the net normal force was non-zero at some point during the collision. This is a consequence of Newton's Second Law.
Consider the acceleration of the clay/cart system as the clay is colliding with the cart. The clay has an upward acceleration, since it is being slowed down in the vertical direction by some force. Because of this vertical acceleration, the clay-cart system must also have a vertical acceleration during the collision. This means that the normal force during the collision will be higher than the normal force without any motion.
The standard concept of normal force = gravitational force only applies in situations where the system is not accelerating and $F = 0$. However, during the collision, the clay-cart system accelerates up. The situation is similar to the case of a scale in an elevator. As the elevator accelerates up or down, the overall force measured by the scale will change due to the acceleration of the system.
Consider the motion of the center of mass in the x-y plane before the collision, and this will be conserved afterwards. For example, if a very heavy ball of clay car was thrown with a high velocity directly into the path of a very slowly oncoming small toy car, the car's speed would likely increase by changing its direction. The center of mass of the original system was moving left rapidly, and so the center of mass of the clay-car system will also move left rapidly. To justify this with Newton's Laws, use the fact that the net force on each object in the collision is equal.
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.
Best Answer
The momenta of individual objects in a collision do change (no matter whether it's elastic or inelastic). However, the total momentum is conserved (does not change), again, irrespective of the fact that the collision is elastic or inelastic. Thus there is a non zero, and in fact equal and opposite impulse on both the objects. Due to this equal and opposite impulse (caused by the normal force between them), the net impulse on the system of those two objects becomes zero and thus the net momentum of the system is conserved.