PCを買い換えてから、「近くのMediaServer」を探させると、発見できなかったり、できてもそれまでに数分かかるようになりました。
（今までは長くとも数秒で発見できていた）

その場合でもMediaServerを起動しているPCのローカルIPを直打ちすれば即座にMediaServerに入るので、最悪PCのDHCP割り当てを固定してしまえばいいのですが
なんか気持ち悪いので原因の手がかりになりそうなことがあれば教えていただければ幸いです。

環境:Windows7 64bit, CGMediaServer2.21(2.11?)
自動検出設定が無効ということもありません。

ComicGlassをご利用ありがとうございます。

はっきりとはわかりませんが、UDPのパケットがロストしているのかもしれません。
LAN内部でその他の高速なデータ転送を行っていることはありませんでしょうか？