Fair, but what do all the advantages amount to if you can't score a kill with her? A lot of her difficulty comes from actually sealing the deal and in FG i've never experienced more than one shiek able to perfectly graph out a combo that killed.
As a Sheik main, I know full well what you're talking about, but I feel her lack of kill power is exaggerated. Her smashes can kill at reasonable percents(minus down smash, arguably her worst), Fair strings can take an opponent from one side of the stage to the next at mid percents, allowing for early kills with bouncing fish. Uair is fairly solid and up-B has amazing kill power.
She needs a nerf, though I can't say for sure what's the most appropriate way to do so.