If everything else checks out, you could have a defective master cylinder. These things are put together by human beings and ....., well you know the rest of the story. The wrong cup and piston would give you a lot of trouble. A defective residual valve would allow air in through the wheel cylinders when the pedal is fully released.
