Yoshi has great recovery now you just have to remember that 2nd jump is vertical and egg toss is the horizontal. When you get knocked off the stage the 2nd jump will take you so high you're off screen and you can normally get to the middle of a stage before you can even see Yoshi again.
Something else to keep in mind is that hovering with the egg toss does take a bit of skill. You can't simply hold up+right+B to jump right. It's all about Yoshi's current momentum. If you pay very close attention in the video you can see that I don't egg toss rapidly, I let Yoshi fall to the right first, then I egg toss. It's brief but necessary. If you don't continue to give him momentum he will egg toss in place and end up falling without moving an inch to the side. Don't let that scare you though, this video wasn't a fluke, I can now do this jump like clockwork and you should all be able to do the same once you get a feel for the character.