PDF関係の説明を見ると、「埋め込みが許可されていないフォント以外は埋め込みが可能です。」と書いていることがありますが、実際、埋め込み出来るフォントなのかどうかというのは、自分の経験のみから導き出せるものではありません。なにしろ、フォントの数は膨大なのです。
このページで、埋め込めるフォント・埋め込めないフォントの一覧を集めましょう。
[225789]フォントを埋め込んだ PDF ファイルを配置すると印刷できない(InDesign CS)
に詳細な情報があります。
Word 2003 にて、HGゴシックM(Office 2003付属)を使い、Acrobat PDF Maker 7 for Word を使って、フォント埋め込み PDF を作り、InDesign CS、InDesign CS2 それぞれに配置し、プリントから PS ファイルを作るという試験をしてみました。
また、InDesign CS 2 から書き出した後の PS ファイルを Acrobat Distiller 7 で 変換したところ正常終了しました。
InDesign CS 2 において、何らかの対応がとられていると考えられます。