「Reader DC 2021.005.20060 Japanese for Windows」時点で下記現象は解消されておりました。
参考程度で確認いただければと思います。
PDFでAdobeリーダのみ文字が正しく読めないといった問題が発生した。
現象
とあるPDFを開くと下記エラーダイアログが表示される。
「MS Mincho」フォントを検出または作成できません。一部の文字を正しく表示できない場合や、印刷できない場合があります。

文書のプロパティを見てみると実際のフォントが不明になっています。
Adobe製品以外(例えばChromeやEdge、その他フリーのPDF閲覧ツール)だと正常に見えます。
PDFを再作成すると、上記現象は改善される場合がありました。
なぜこのような現象になるのか調べることにしました。
テストPDFのダウンロードはこちら
原因
場所の特定
PDFリファレンスと突合せながら読み解いていくと「/Registry」項目の値がよろしくないっていうことがわかりました。
「Registry」には「Adobe」が入ります。
10 0 obj
<<
/Registry (Adobe)
/Ordering (Japan1)
/Supplement 6
<blockquote>>
endobjPDFにパスワードをかけると、Adobeの部分が暗号化されます。
10 0 obj
<<
/Registry <FEFF3E18C0>
/Ordering <F5FA211BCB22>
/Supplement 6
<blockquote>>
endobjPDF作成ツールによっては、「/Registry <FEFF3E18C0>」の赤太字部分がバイナリデータに変換されている場合があります。

通常バイナリデータになっていた場合でも正常にPDFを表示することができるのですが、Adobeの場合、特定のバイナリデータが来た場合うまく復号処理ができていないようです。
例えば、上記バイナリデータ化されたPDFをAdobeで表示⇒パスワードロックを解除した状態で保存すると「/Registry <Adobe〇>」といった余計な文字がついていました。
これが原因でうまくフォントが読み込めないようです。

FEFFから始まると復号できない
他に文字化けするPDFとを見比べると、「/Registry (****)」の部分(バイナリデータ)の配列がFEFFになっていると文字化けが発生するようです。

↑画像にてカーソルで反転している部分が「FEFF******」になってたらAdobe Readerではうまく開けないようです。
再作成すると正常になる理由
「/Registry (****)」の()内はパスワードが設定されている場合、PDFのIDによって異なる値になります。
IDというのは、PDFに一意を決めるようになっており、基本的にPDF作成の度に異なる値になるようです。
0000000474 00000 n
0000000594 00000 n
0000000718 00000 n
0000000802 00000 n
0000000996 00000 n
trailer
<<
/Root 1 0 R
/ID [(4253DEE41D1A85254C03DADC1000CD39) (4253DEE41D1A85254C03DADC1000CD39)]
/Encrypt 12 0 R
/Size 13
<blockquote>>
startxref
1204
%%EOFその為、暗号化された文字列が変わる為2回目はうまくいくという理由です。
条件
下記現象にて発生するようです。
- Adobe DC (~2018.011.20038)←Reader含む
Adobe Acrobat Pro9では発生せず - フォントが埋め込まれていない
 - パスワードロックがかかっている
 - /Registry(Adobe)の()内部分がバイナリデータでFEFFから始まる
Adobe以外の文字列は未検証
/Ordering()の場合、現象発生せず 
暗号化レベルはRC4 40bits、RC4 128bits共に発生しました。
AESは今回検証したツール(PDFbox1.8.13)では読込のみ対応(作成できない)為確認できていません。
下記ファイルにそれぞれのテストデータ置いておきます。
RegistyがFEFFのパターン
OrderingがFEFFのパターン(現象発生せず)
対応策
「/Registry (バイナリ文字列)」を「/Registry <HEX(16進数)文字列>」に変換すれば開けるようです。
()がバイナリ文字列、<>がHEX文字列として解釈するようです。
PDF作成しているところが多く、確率的にも1/65535ですし結構問題になりそうな気がするんですけど、今はそうもないんですかね。
クロスプラットフォームに対応するならフォント埋め込みした方がいいし、今じゃ少数派なのかもしれません。
Adobe社対応待ちですね。
「Reader DC 2021.005.20060 Japanese for Windows」で解消されました。
テストソース
PDFBox1.8.13でテスト用PDFを作成しました。
Registry及びOrdering内の文字列をバイナリ化するにはそのままではできなかった為、一部ソースを修正しています。
//バイナリデータで実行できるように修正
/**
* Forces the string to be serialized in hex form but not literal form, the default is to stream in literal form.
*/
private boolean forceHexForm = false;
private boolean forceBinaryForm = false;//←追加
・
・
・
public void setForceHexForm(boolean v)
{
    forceHexForm = v;
}
//バイナリ強制出力設定の追加
public void setForceBinaryForm(boolean v)
{
    forceBinaryForm = v;
}
・
・
・
/**
 * This will output this string as a PDF object.
 *
 * @param output
 *            The stream to write to.
 * @throws IOException
 *             If there is an error writing to the stream.
 */
public void writePDF(OutputStream output) throws IOException
{
    boolean outsideASCII = false;
    // Lets first check if we need to escape this string.
    byte[] bytes = getBytes();
    int length = bytes.length;
    for (int i = 0; i < length && !outsideASCII; i++)
    {
        // if the byte is negative then it is an eight bit byte and is
        // outside the ASCII range.
        outsideASCII = bytes[i] < 0;
    }
// if (!outsideASCII && !forceHexForm)
if (forceBinaryForm ||(!outsideASCII && !forceHexForm))//←バイナリ判定できるように変更
[/java]
[java title="MakePDF.java"]
package test;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import org.apache.fontbox.util.BoundingBox;
import org.apache.pdfbox.cos.COSArray;
import org.apache.pdfbox.cos.COSDictionary;
import org.apache.pdfbox.cos.COSName;
import org.apache.pdfbox.cos.COSString;
import org.apache.pdfbox.exceptions.COSVisitorException;
import org.apache.pdfbox.pdmodel.PDDocument;
import org.apache.pdfbox.pdmodel.PDPage;
import org.apache.pdfbox.pdmodel.common.PDRectangle;
import org.apache.pdfbox.pdmodel.edit.PDPageContentStream;
import org.apache.pdfbox.pdmodel.encryption.AccessPermission;
import org.apache.pdfbox.pdmodel.encryption.BadSecurityHandlerException;
import org.apache.pdfbox.pdmodel.encryption.StandardProtectionPolicy;
import org.apache.pdfbox.pdmodel.font.PDFont;
import org.apache.pdfbox.pdmodel.font.PDFontDescriptorDictionary;
import org.apache.pdfbox.pdmodel.font.PDType0Font;
public class MakePDF {
public void make(String id_text, String path) throws COSVisitorException, IOException, BadSecurityHandlerException {
PDDocument document = new PDDocument();
PDPage page = new PDPage();
document.addPage(page);
    //権限設定(PDFのバージョンによって使える権限は異なる。今回はV2、Revesion3とする。
    //-60…文書の変更及びコピー・抽出禁止
    AccessPermission ap = new AccessPermission(-60);
    //パスワード設定
    StandardProtectionPolicy spp = new StandardProtectionPolicy("password", "", ap);
    spp.setEncryptionKeyLength(40);//RC4 40bits
    document.protect(spp);
    //フォントグリフの設定
    COSDictionary systeminfo = new COSDictionary();
    /**
     * フォントグリフの設定
     * バイナリデータで挿入できるように、COSString.javaを書き換える
     */
// systeminfo.setString(COSName.REGISTRY, "Adobe");
// systeminfo.setString(COSName.ORDERING, "Japan1");
COSString registry = new COSString("Adobe");
COSString ordering = new COSString("Japan1");
registry.setForceBinaryForm(true);//true:バイナリデータで出力 false:HEXデータで出力
ordering.setForceBinaryForm(true);//true:バイナリデータで出力 false:HEXデータで出力
systeminfo.setItem(COSName.REGISTRY, registry);
systeminfo.setItem(COSName.ORDERING, ordering);
systeminfo.setInt(COSName.SUPPLEMENT, 6);
    //フォント書体設定
    PDFontDescriptorDictionary fd = new PDFontDescriptorDictionary();
    fd.setFontName("MS Mincho");//MS明朝
    fd.setFlags(4);
    fd.setFontBoundingBox(new PDRectangle(new BoundingBox(-500, -300, 1200, 1400)));
    fd.setItalicAngle(0);
    fd.setAscent(1400);
    fd.setDescent(-300);
    fd.setCapHeight(700);
    fd.setStemV(100);
    //CIDフォント設定
    COSDictionary cid = new COSDictionary();
    cid.setItem(COSName.TYPE, COSName.FONT);
    cid.setItem(COSName.SUBTYPE, COSName.CID_FONT_TYPE0);
    cid.setItem(COSName.BASE_FONT, COSName.getPDFName("MS Mincho"));
    cid.setItem(COSName.CIDSYSTEMINFO, systeminfo);
    cid.setItem(COSName.FONT_DESC, fd);
    //フォント設定
    COSDictionary font = new COSDictionary();
    font.setItem(COSName.TYPE, COSName.FONT);
    font.setItem(COSName.SUBTYPE, COSName.TYPE0);
    font.setItem(COSName.BASE_FONT, COSName.getPDFName("MS Mincho"));
    font.setItem(COSName.ENCODING, COSName.ENCODING_90MS_RKSJ_H);
    COSArray array = new COSArray();
    array.add(cid);
    font.setItem(COSName.DESCENDANT_FONTS, array);
    //テキスト入力
    PDPageContentStream stream = new PDPageContentStream(document, page);
    stream.beginText();
    //フォントとフォントサイズの設定
    PDFont pdFont = new PDType0Font(font);
    stream.setFont(pdFont, 36);
    //文字の配置設定
    stream.moveTextPositionByAmount(50, 300);
    //文字列をMS932のバイト列にしつつ、ASCIIコード(1byte文字列)として出力
    stream.drawString(new String("テストPDF".getBytes("MS932"), "ISO8859-1"));
    stream.endText();
    stream.close();
    /**
     * 引数のID情報を設定
     * 指定しなければID部が<>で自動挿入され、指定すれば()で挿入される
     */
    if(id_text != null) {
        COSString id = new COSString(id_text);
        COSArray idArray = new COSArray();
        idArray.add(id);//登録ID
        idArray.add(id);//更新ID(同一)
        document.getDocument().setDocumentID(idArray);
    }
    document.save(path);
    document.close();
}
/**
 * PDFのRegistry部分に「/Registry <FEFF」が存在しないかチェックする。
 * @param filePath ファイル名
 * @return true:存在
 */
public boolean checkFEFF(String filePath) {
    FileReader fr = null;
    BufferedReader br = null;
    try {
        fr = new FileReader(filePath);
        br = new BufferedReader(fr);
        String line;
        while ((line = br.readLine()) != null) {
            Pattern p = Pattern.compile("Registry <FEFF");
            Matcher m = p.matcher(line);
            if(m.find()) {
                return true;
            }
        }
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    } finally {
        try {
            br.close();
            fr.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    return false;
}
}package test;
import java.io.IOException;
import org.apache.pdfbox.exceptions.COSVisitorException;
import org.apache.pdfbox.pdmodel.encryption.BadSecurityHandlerException;
public class Run {
public static void main(String[] args) throws COSVisitorException, IOException, BadSecurityHandlerException {
/**
* 調査用
*/
//ID元となるデータの作成
int int_id = Integer.parseUnsignedInt("1000BD48", 16);
String filename = "test.pdf";
long count = 0;
while(true) {
String id = "4253DEE41D1A85254C03DADE" + Integer.toHexString(int_id++).toUpperCase();
        MakePDF makePDF = new MakePDF();
        makePDF.make(id,filename);
        if(makePDF.checkFEFF(filename)) {
            System.out.println("発見(" + id + ")");
            break;
        }
        if(count % 1000 == 0) {
            System.out.println(count + "件確認");
        }
        count++;
    }
    /**
     * 再作成用
     */
// MakePDF makePDF = new MakePDF();
// makePDF.make("4253DEE41D1A85254C03DADE10023A21", "test.pdf");
}
}