結果として、Windows版Python3.8でのctypes.LoadLibrary仕様変更、os.add_dll_directoryの追加の話です。
つまり、ライブラリのサーチで単純にPATHを参照しないということでした。

ハマったこと

Windows, Python 3.9で自前のmylib.dllを使いたい。
mylib.dllはdep.dllに依存している。

mylib.dllとdep.dllが同じディレクトリにある時は問題ない。

import ctypes
dll = ctypes.CDLL(R"path\to\mylib")

ところが、dep.dllを他のディレクトリに追いやってPATHを通したうえで同じことをすると

FileNotFoundError: Could not find module 'D:\XXXX\path\to\mylib' (or one of its dependencies). Try using the full path with constructor syntax.

などと言われる。

解決

os.add_dll_directoryを使って、dllのディレクトリ（サーチするパス）を明示的に与えてやれば解決した。

このissuesは正直いってよく分からなかったので、
今回は単純に環境変数PATHをadd_dll_directoryに与えちゃうことにします。

import ctypes
import os

dll = ctypes.CDLL(R"path\to\mylib")
# FileNotFoundError: Could not find module 'D:\xxxx\path\to\mylib' (or one of its dependencies). Try using the full path with constructor syntax.

for p in os.environ['PATH'].split(os.pathsep):
    if os.path.isdir(p):
        os.add_dll_directory(p)
    
dll = ctypes.CDLL(R"mylib")
# 問題なし

これの問題は？

なんでこんな仕様になっているのかちゃんと調べていないが、PATHをそのまま使うのに何か危険があるのかもしれない。
解説か他の賢い方法があったら教えてください。