Actually, it is very likely not a lack of font embedding, this problem is usually caused by documents that do not contain all the information that Acrobat needs to extract text.
Converting a PDF file to any other format is one of the most complex things you can do with a PDF file. Text extraction will only work if everything that is necessary to map a glyph (that is the "drawing" of a character that you see on a PDF page) back to a character is stored in the PDF file. Cheap (and sometimes not so cheap) PDF generators oftentimes take shortcuts by not adding such a table for each font that is used to the PDF document. This does not affect these files as long as you only want to view them or print them, but as soon as you try to extract data, you will run into these problems. Complain to whoever provided these PDF files and ask them to use a better application to create the files.
Karl Heinz Kremer
PDF Acrobatics Without a Net
PDF Software Development, Training and More...
http://www.khkonsulting.com