Hi, Cleaning the outside unit will not help your air flow. what it will do is work more efficiently, It will cool or heat(heat pump) the air better. Sorry but it wont solve your air flow problem. Some item's to check, the insulation under the home, connection of the duct work, Even check the air filter and make sure its clean. You said that they cleaned the A coil, so that should be okay. Also take a different thermometer and put it by your thermostat and see if your thermostat is reading the same temp. Hope this helps.
Please remember to check and change your filters.