I am afraid to say that I mostly have negative things to say about this MU. I played M2K's Sheik on FG for 2 hours a little while back with my Falco, didn't think it was him until I saw his ledge game. Yes... it was him.
Perhaps it was the vast difference in skill, but I would argue that a great Sheik can best Falco's gimp game any day. Sheik is just too fast, and that is a big issue. The thing is that by 70% if his sheik ever got me to the ledge of a stage, then it was near impossible to recover. Sheik's fair is just too fast. he would actually grab the ledge and wait for me which resulted in 2 situations. I could either use phantasm and try to recover above the ledge or sweet spot the ledge, but then M2k would react to it and drop off the ledge into bair or nair (he never missed the reaction...period). Phantasm is useless to sheik because we can't shorten it. This took a lot from our recovery mind games, but phantasm does have a use on battlefield where there are platforms to dampen the punishes (I never reaped the benefits though as we played on FG).
If I recovered low, then he would stage spike me, without fail. If I got the tech he would quickly move back to the ledge and punish accordingly with bair/nair/fair which he had plenty of time to do. Sometimes he would just teleport after the tech and still catch me in a second stage spike. I still cannot see any option that would have kept me in the game. He also used her needles to take away my second jump or delay my phantasm and force me into a low recovery up-b, which promptly would end in a stage spike. Recovering low was a big NO on this MU. I found that I could survive by recovering high because he would make a mistake, but he always could punish my landings in the end.
When I tried to gimp him, he would always use her needles to stop fair, teleport, then punish me to death, so I seldom tried gimping after that. He would even trade hits with Sheik's teleport, which unfortunately ends badly for falco if a Sheik can time it well. She just has so much stage control that it's crazy hard to deal with her.
I admit, I am nowhere near M2K's level, and he is someone very experienced with gimping Falco. Still, I must say, trying to gimp a good sheik=very risky, but not impossible I am sure. I sure as heck never gimped M2K in our matches. He seldom two stocked me though, which I considered a win lol. I almost always took the stock using dtilt, usmash, and bair which kill relatively early since Sheik is so light.
In summary, recover high and you get punished. Recover low and you get punished. Air dodging from high recovery just isn't possible with Sheik because her fair is so fast. If you air dodge, she can go into another fair before you can air dodge again. There is no reason for Sheik not to approach you in the air. I tried fair, but M2K always reacted to it because it came out too slow. Same issue with dair. Furthermore, falco has no horizontal movement while in the air, so it is just disastrous if a good sheik gets you in the air, which she can do easily with about 50% of her moves (utilt, ftilt, dtilt, grab, fair, uair, usmash). Maybe fast-fall fair can work, but it seems way too risky and I never profited from it. Bair is your best bet, but he never went behind me for that reason alone and Falco lacks the tools outside of neutral to position an Sheik into the bair.
HOWEVER; in neutral game I did have some success. Combos off of utilt and nair actually did happen because Sheik does have to space a little close to you sometimes. I also challenged his fair with my fair and won. The main issue is Sheik's f-tilt. If M2K and any sheik for that matter manages an f-tilt on me, it is pain city straight to 50-60% without fail. M2K typically could position to the ledge off of one mistake by using his f-tilt combos, and as you can imagine it typically meant death at that point. In contrast, if I did manage a hit, I usually got a good 40-50% on Sheik myself (this includes M2K's sheik) and this was at a time where my falco's punish game was in its infancy. Still, good luck getting that punish. Sheik is just overall very, very safe. I had to do hard reads for those punishes. Make them respect the bair and dtilt. Those seem to be the best tools against Sheik because of their spacing. Dtilt is pretty good since it usually combos into fair/bair. Her combo game definitely depends heavily on her getting within those hit box range, so just make it as difficult as possible for her to get in by using those.
Pre M2K, I placed the MU at 40;60 Sheik's favor. After my matches with M2K, it felt more like 30:70. But, then again, I am not at that competitive level, so take it skeptically. I just don't use Falco against Sheik anymore. I prefer Link or Fox for this one.
Sorry about the wall of text! Good luck on this MU, it is truly an uphill battle.