Have you tried Silver Airlines I think they fly from Fort Lauderdale to Key West also Cape air may be worth a look.Not sure what type of aircraft you are flying but I've flown into EYW dozens of times in the CRJ 700/900 also Delta flies a 737 into EYW.Maybe it's a parking problem as the GA ramp is pretty small.