Okay, I'm answering my own quesion, but it's for the benefit of others trying to do the same thing.
My mistake was missing the -inkey parameter to openssl. So, assuming you have followed the precise instructions in the Breezy howto (http://www.howtoforge.com/perfect_setup_ubuntu_5.10)
, you can create a certificate for Outlook using the following:
openssl pkcs12 -export -in smtpd.crt -inkey smtpd.key -out OutlookSMTP.p12
Then import the OutlookSMTP.p12 file into the Trusted Root Certification Authorities store within Internet Explorer (Tools -> Internet Options -> Content -> Certificates, or by just double-clicking it). You will then be free to establish an SSL connection within Outlook to enforce tighter security.
Hope this helps others. Perhaps this HOWTO could be edited to put this as an optional step?