You dont have to block to evade throws.
Simply hold back, or down-back to get not throw.

For Sheeva the only way (and easy) is to simply walk or run forward to evade the stomp attack.
For Kintaro the best way to counter the stomp attack is to jumpkick backward.

Sonya,s Leg grab is a special moves exactly like Kano,s grab special, thats why you can evade it by pressing block.

And forget everything I wrote when you play against the AI, the throw rules dont count for it.

Some moves can counter Sheeva's stomp, like certain uppercuts, Kung Lao Spin, you can spin Sheeva out of it with Kabal, air throw with anyone, jump away and kick, but your best bet is to walk backwards, let her land next to you and then punish her.

I can't help you with Kintaro or MKII AI throw situations, but I know that the same goes for UMK3, you can't prevent throws against the computer and it's almost impossible to throw them in any conventional situation after a certain difficulty level. In UMK3 during Finish Her, I once tried to do a just frames throw (meaning I threw as soon as fatality time ran out) with Sub-zero on Kitana as she was falling over so I could throw her off the screen so it would look funny, but Kitana threw me instead, then died.

Sonya's leg grab can only be blocked low, like Stryker's baton trip.

Throw prevention is just simply "Hold Back", but usually D+B is better, and often times you're going to want to be blocking as well, so most people think it's D+B+BL. I find it easier to hold back+block, and if they go for a low attack, just switch blocking to low and block only the necessary frame of attack, allowing me to attempt to rush in after.

A straight up jump kick knocks kintaro out of a stomp, allowing juggles for people with air moves.