Check Toys R Us maybe, for the Pokemon and maybe Sonic ones. The Mario plushes I remember have been out of production for years. (There was a really good set of small and big Mario and Luigi plush toys produced in the '80s from Applause, I think.) If I still had them, I'd donate them to your baby. The later ones from BD&A are good too if you can find them.
There are a few Pokemon plushes at a local comic shop I may be able to pick up, if you'd like next time I go shopping for games. They're the small early run plushies from Hasbro. I also have a medium plush Pikachu and Jigglypuff that I'll have to clean up a bit if you're interested.