そもそも本当にデッドロックが問題なのか？ていう問題もあるし。
漏れとかはペイント側は完全に変数の解釈->描画だけに集中していて
ペイント側が実アプリ側には影響しないはずのドキュメントビュー構造を
徹底したにもかかわらず、どうも描画のリクエストが変なタイミングで
飛んできて絵が（たまに）壊れる等の理由で、結局
本体、描画コールバック双方を完全にSyncｈronizedした
同期型のプログラムで決着つけた。

機種依存の性か、音の出方に若干影響がでちゃったんだけど、
それはまあさておき。

基本的にペイント側は、元から出来上がってる情報を噛み砕いて
絵にする作業に徹してる限り（例えばペイント側が本体ルーチンに
参照される変数やオブジェの加工をするとかでない限り）、
デッドロックって起きようがないはずなんですよ。

こと、双方からsynchronized外して（挙動こそ変われど）デッドロック
状態を脱しないなら、スレッドが悪さしてる可能性を一度捨てて
コード全体を再検証したほうがいい。

時間が許すなら、各コンポネントの依存関係図とかも、ちゃんと書いた方がいいすよ。
ロックが起きる状況＝アトミック（不可分な処理）の中でさらに他のコンポネントにチョッカイかけてるとか
アトミックと定義されてるオブジェクトの生成結果ではなく、途中の生成物に期待してる
オブジェがいるとか、その類なんだから。