The problem you could be experiencing could be more related to the phenomenon of "mass transport" than anything else.
Basically, for a reaction to occur the two reactants need to get close to each other. It could be that a catalyst works by forming a reactive complex with the reactant and carrying it through multiple reactions.
Essentially, the catalyst is speeding up the reaction but is caught up in the reaction while it is occuring. If there isn't enough catalyst for every single reactant, some of them are occuring at the catalyzed speed and others are proceeding normally; adding a little more catalyst just ensures that a higher percentage of substrates are being assisted by the catalyst at the same time.
Imagine the following scenario: A room full of people trying to cut sheets of paper in half. Everyone is using scissors, and there is one movable, industrial paper cutter being passed around. The guy who has the paper cutter is going to move much more quickly while the paper cutter is at his station. Additionally, the paper cutter has to be with him the entire time he is cutting, or else he slows down. The paper cutter is the catalyst.
If you add more paper cutters, you would keep speeding up. It isn't because the paper cutter disappears or stops working; it's because not everybody has a paper cutter.