How can I get Apple mail or Outlook 2011 to look up SMIME encryption certificates for users?
According to the Apple TS article "Using Keychain Access to search directory services for certificates", if your Mac


is configured to use a directory service,
has the CA signing certificate trusted in either your login or the system keychains,
has a valid signed user certificate with the appropriate attributes,


then Keychain Access can be configured (Preferences → General → Search directory services for certificates) to search for certificates on the configured directory service.  Mail.app will also automatically search for certificates as well.

Unfortunately, I haven't done this personally, so I can't vouch for how well it works or have any advice on any issues.  This reads to me like a feature designed to be used with a centrally-managed IT infrastructure with directory and certificate services.  It does not sound like it is designed to work outside that sort of environment.