Here are a few common scenarios where I *don't* think you'll need to search for user certificates: [..] 3) Verifying signed email
In all of these cases, you will already have the user's certificate in hand.
The primary use case where I expect you will need to find someone's user certificate would be when you want to send an encrypted email to someone whose user certificate you don't already have.
I support the proposal made by Peter Gietz since it seems like an fairly easy solution to me solving some real-world problems.
Can't certificateMatch do as well?