The typographer was either lying or misinformed. (Unless he just meant of Papyrus in particular.) Lots of clones are legal so long as they are made independently, and the original design of the fonts are in the public domain. (As most of the classics are.)
Otherwise, how could it be that each of the major foundries has its own (slightly different) version of Garamond, or Baskerville, or Times?
Others were donated into the public domain, such as Bitstream Charter, which is cloned in unequestionably free and legit fonts like Charis SIL. Same goes with Knuth's Computer Modern and clones/derivatives like GUST's Latin Modern.
Font Squirrel is definitely on the up and up, and the Larabie fonts are free to add with the Font Face tag. They just ask you to obscure their names so they're not easy to guess.
details here -- Font Squirrel has a @font-face generator that actually changes the names of the fonts during the process.
I can't imagine that doing that would even be necessary for ePub embedding, since it'd be a hassle to get them that way anyway.
Still, I agree with your advice to try to track down and visit the actual foundry or designer's website -- sometimes you learn a little about the font and its vision that way too, which is interesting. I particularly like
The League of Moveable Type, which has a number of high-quality generous license fonts (listed on Font Squirrell).