Sheik on FD is a challenge for sure... the main problem I have with parrying grabs is that they're often difficult to predict, and you can't react to them since most have very little startup (~7frames) and there's no real giveaway cue like an aerial or a laser has (jumping). This is less of a problem with Sheik than with Fox/Marth/Falcon since Sheik's dashdance is terrible, but she still has the option of wavedashing back or ftilting instead of the grab, and she can force approaches from you with needles (these are so annoying on FD!!!) and then grab you during landing lag/whatever mistake you might make. It's nice that we have the option of jumping out of the parry if it was unsuccessful and we need to get away, but this is unfortunately not possible if your intention is to grab, since our reaction time isn't really fast enough to check before jumping or grabbing.
I prefer to go with safely spaced aerials to bait out a whiffed shieldgrab (Fair is good for this), and I imagine parrying the wavedash > grab out of shield would be a very useful tool if I ever play a Sheik who doesn't fall for the spaced Fair (or Bair crossup). Unless of course the Sheik decides it's time to approach, in which case crouch cancelling is very useful for Yoshi. On any stage with platforms I feel that Yoshi has much more control than people think in this matchup, and I really like how Kimimaru makes use of them. He's very careful with his approaches and his platform use seems to pay off since Sheik can't really do much about it and if she tries, she's likely to end up in a bad spot while you're zipping around the stage.
One trick I see aMSa do a lot (and it really works well) is to use aerials to bait out something you can parry. He often does this with a retreating Fair, at just the right distance that his opponent thinks they can dash forward and SHFFL something (like Fox Nair), but by the time they get to him, the Fair landing lag is over and he parries. You could try something like this with Sheik's grab if you can recognize what will make your opponent go for the grab. This will probably be specific for each player, potentially different every time but also maybe limited to one of a few things that reliably work against Sheik mains.
I agree with what you have to say about exploiting what you know they'll do. I think I just have a different way of going about it (I'll admit parrying grabs is one thing I can't do consistently yet, but I'm not sure if I'd be doing it if I could anyway). Generally, I've noticed this about the Sheik matchup: if they're bad and they know about the chaingrab, they'll go for raw grabs in the neutral game, so I bait those out. If they're good, they'll use Sheik's more reliable pokes (aerial needles or Ftilt etc) and it's much tougher to deal with, but I think if you intend to use parrying in this matchup, make sure that you're prepared for those options as well.
And as always, a good punish game makes a world of difference for Yoshi