Ok, let's break this down a bit. A/C systems have two basic modes:
When you are in outside air mode, the vehicle will allow air from outside the cabin to enter.
Recirculate means that the vehicle will mostly use the air already inside of the cabin.
Note that both modes allow air to be from both sources. You will get outside air in recirculate, and you will recirculate in outside air. What you change is the amount.
The common approach to cooling a hot cabin is to turn on the A/C and let outside air in. This is done to replace the hot inside air with fresh outside air. Once the hot air has been replaced, the recirculate mode is turned on to increase the speed air is cooled inside the cabin. Its easier to cool air that has been recirculating inside the cabin than outside air.
Why does MAX A/C work for you?
In modern cars, the MAX A/C settings gets an initial burst of outside air in the first few seconds of operation and then starts to recirculate it. It is a hybrid setting that allows you to get cold air as soon as possible. If you car has an intelligent multi mode climate control system then you are going to have to ask the weather guy to help you figure it out. :)