I ran into this problem the other day.  Use Windows/IE to import your 
self-signed SSL cert. After importing, the cert can be viewed with IE 
(Tool->Internet Options->Content->Certificates->Trusted Root 
Certification Authorities) .  From this menu, export your cert to a 
file.  (Repeat the import/export procedure if you have more than one SSL 
cert.)  Anyone connecting to your mail server w/ Outlook will have to 
import/install your exported cert(s).

-Cha

Nate Carlson wrote:

>I know it's OT, but we use Linux mail servers, so that makes it on topic,
>kinda.  :)
>
>>From Outlook 5.5sp2 on, it appears Microsoft actually checks to make sure
>that the SSL cert of the remote POP/IMAP server came from one of the
>recognized CA's, and puts up an annoying popup if it isn't. Anyone know
>how to either install another CA, or just tell OE to accept the cert? Of
>course, they can't make it easy like in Mozilla/IE (just click accept it
>permanently.. heh)..
>