たぶん質問者の方が俺よりずっと詳しそうだから釈迦に説法だと思うけど、

＞●例えばこれだと、デッドロックを引き起こすので良くない
＞lock(obj1) lock(obj2) 処理;

これがデッドロックしうるのはこのスレッドがobj1だけをロックした状態で
別のスレッドがobj2をロックして、そのスレッドがobj1を待機してる場合だよね？

この場合このスレッドがobj1をアンロックしない限りobj2もアンロックされないからデッドロック

だから、ネストの内側のock(obj2) だけをタイムアウト付きのMonitor.TryEnterに置き換えれば
効率的かどうかはどうかはともかく、要件は満たせるんじゃいないの？
知らんけど