I can think of two choices here (there may be more... and if someone supplies another I will be learning too):
Choice 1 - turn off encryption (edit the email account, click 'more settings' and on the advanced tab set the dropdown for secure connections to 'none'
Using this choice your email in no longer encrypted between the server and outlook. (this is also the method that Outlook 'discovers' by default if you use the new account wizard to add the account.)
Choice 2 - if you need the encrypted connection, leave your setup as is and deal with the warning.
Dreamhost could, as you suggest, issue a certificate for each mail domain. However, if they issue a 'self-signed' certificate like the one currently in use for mail, it still would not solve the problem as windows would report "Windows does not have enough information to verify this certificate." and the same error dialog would be presented.
If dreamhost issued a 3rd party (verisign, etc) certificate for each email domain they would have to charge us the 3rd party fee (+profit) for the certificate.
AFAIK, if you need encrypted email you have to deal with the warning, if non-encrypted email works for you then turn off encryption and the error goes away.
Perhaps a window's registry edit exists to suppress the dialog as well, but I've never looked for it.[hr]
As an afterwards to this post, the 3rd option is to switch your email handling over to gmail....[hr]
I also just found this article over on micro$oft technet: http://blogs.technet.com/b/asiasupp/archive/2007/05/29/self-signed-certificate-issue-when-connecting-to-the-exchange-server.aspx
It's old and it is written in "vista" speak, but you may be able to adapt the information to work with whatever your current win/outlook version are.