Cooling is tough. There's going to be a trade off of some kind, you don't just get faster cooling without expense of some kind. Without a huge capital investment, there's a couple things you can try.
1. Have you tried keeping the racks in your refrigerator to pre-chill them? Then transfer the cooked muffins to the pre-chilled racks before placing in the refrigerator. Then the refrigerator doesn't have to also cool the room-temperature (or baked?) racks as well as the muffins, and the trays will cool more quickly at the contact points with the racks. Cost: Transfer labor or inconvenience.
2. Probably the easiest option, skip every third "row" of your racks to allow for additional space on one side of each tray. This will make existing airflow systems work better and reduce the overall "heat" load of the system. Cost: fewer muffins cooled each batch.
2. Use the fans as mentioned. Cost: yes they do get dirty quickly, and you a right to address these as a safety risk. FDA loves to go after dirty fan blades, especially in bakeries. Check the warning letters and use them as examples for management to demonstrate why they'll have to invest the labor to keep them clean.