I see one of three possibilities here:
1. One of the galley plugs on either end of the block are leaking or missing. If the back plug was missing you would have oil ccoming out of the bellhousing. If the front plug were leaking it would run down the front of the engine.
2. Your pressure regulator on the pump needs some additional work. It may stuck in the relieving position and thus bleeding off pressure or you may need to shim the spring in the pump to create the desired pressure.
3. The pump is worn internally to the point where it cannot build a normal level of oil pressure.
Typically, the pump either works or doesn't work at startup with only internal priming before installation. I highly doubt that air is causing any of these issues (unless you have an air leak on the suction side of the pickup)...