以下のようにしようと思います。
まず、署名の検証に成功した場合には、署名した鍵の長いIDフィンガープリントを使ってその鍵の情報を調べます。そして、その鍵に結び付けられたユーザIDのうち、有効性がultimateかfullyのものだけをリストアップします。そのようなユーザIDがなかった場合には署名検証に失敗したのと同じ扱いになります。
FromかSenderのアドレスがリストされたユーザIDに含まれる場合には、そのユーザIDをSigned byとして表示します。含まれない場合には、リストの最初のユーザIDを表示します。また、前者の場合にはFromの背景色は薄い黄色に、後者の場合には赤になります。
Signed byの背景色は、検証に成功した場合には薄い黄色、それ以外の場合（検証に成功したが有効なユーザIDが見つからなかった場合も含む）には赤になります。検証に失敗した場合（検証に成功したが有効なユーザIDが見つからなかった場合も含む）には、Signed byは表示されません。ステータスバーのアイコンも、前者の場合にはチェックマーク、後者の場合には×マークになります。
S/MIMEの方も同様の表示方法にします。ただし、ステータスバーのアイコンだけは、FromかSenderのアドレスが証明書のメールアドレスに一致しない場合も×になります（PGPの場合にはこのケースでもチェックマークになります）。
ステータスバーのアイコンをクリックすると、PGP処理時の標準エラー出力が表示されます。S/MIMEの場合には証明書が表示されます。
ただし、コマンドライン版のPGPを使った場合にはユーザIDの有効性はチェックされません。GnuPGを使った場合には、上記の通りになります。